Step-By-Step Directions From a Binary Tree Node to Another

Medium
1954.

Step-By-Step Directions From a Binary Tree Node to Another

Step-By-Step Directions From a Binary Tree Node to Another is a medium coding problem on strings, depth-first search and trees, asked in Amazon, Google and Meta interviews.

You are given the root of a binary tree with n nodes whose values are the distinct integers 1 to n, and two different values startValue and destValue.

Return the directions for the shortest walk from the node holding startValue to the node holding destValue, as a string of the letters:

  • L — move to the current node's left child;
  • R — move to the current node's right child;
  • U — move to the current node's parent.

Example 1

Input
root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output
UURL
Explanation
From 3 go up to 1, up to 5, right to 2, left to 6.

Example 2

Input
root = [2,1], startValue = 2, destValue = 1
Output
L
Explanation
1 is the left child of 2.

Example 3

Input
root = [1,2,3,4,5], startValue = 5, destValue = 4
Output
UL
Explanation
Up from 5 to their common parent 2, then left to 4.

Constraints

  • 2 <= n <= 10^5
  • 1 <= Node.val <= n
  • all node values are distinct
  • 1 <= startValue, destValue <= n
  • startValue != destValue
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} startValue
 * @param {number} destValue
 * @return {string}
 */
var getDirections = function(root, startValue, destValue) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Step-By-Step Directions From a Binary Tree Node to Another Solution

Step-By-Step Directions From a Binary Tree Node to Another solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Step-By-Step Directions From a Binary Tree Node to Another is a medium coding problem on strings, depth-first search and trees, asked in Amazon, Google and Meta interviews.

Problem statement

You are given the root of a binary tree with n nodes whose values are the distinct integers 1 to n, and two different values startValue and destValue.

Return the directions for the shortest walk from the node holding startValue to the node holding destValue, as a string of the letters:

  • L — move to the current node's left child;
  • R — move to the current node's right child;
  • U — move to the current node's parent.

Example 1

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: UURL
Explanation: From 3 go up to 1, up to 5, right to 2, left to 6.

Example 2

Input: root = [2,1], startValue = 2, destValue = 1
Output: L
Explanation: 1 is the left child of 2.

Example 3

Input: root = [1,2,3,4,5], startValue = 5, destValue = 4
Output: UL
Explanation: Up from 5 to their common parent 2, then left to 4.

Constraints

  • 2 <= n <= 10^5
  • 1 <= Node.val <= n
  • all node values are distinct
  • 1 <= startValue, destValue <= n
  • startValue != destValue

Hints for Step-By-Step Directions From a Binary Tree Node to Another

  1. Hint 1

    The shortest walk goes up from the start to the lowest common ancestor of the two nodes, then down to the destination.

  2. Hint 2

    Write down the path from the root to each node as a string of Ls and Rs.

  3. Hint 3

    The two strings share a prefix — the walk to the common ancestor. Drop it; every remaining step of the start's path becomes a U, followed by the rest of the destination's path.

How to solve Step-By-Step Directions From a Binary Tree Node to Another

Both nodes hang off the root by an L/R path. Their longest common prefix leads to the lowest common ancestor; climbing from the start to it is one U per remaining start step, and the remaining destination steps lead down.

Approach

  1. Find the root-to-start path and the root-to-destination path as L/R strings (depth-first search with backtracking).
  2. Let k be the length of their longest common prefix.
  3. Return U repeated len(startPath) - k times, followed by destPath[k:].

Why it works

In a tree there is exactly one simple path between two nodes, and it passes through their lowest common ancestor — the last node shared by the two root paths, reached after exactly k common steps. From the start, len(startPath) - k parent moves reach it, and the destination's remaining steps lead down from there.

Complexity

  • Time — O(n)
  • Space — O(n) for the paths and the recursion

Pitfalls

  • Building path strings by concatenation at every call is quadratic — append to one buffer and backtrack.
  • The common prefix must be compared step by step; do not try to compare node values along it.

Reference solution

Python

from typing import Optional

def getDirections(root: Optional[TreeNode], startValue: int, destValue: int) -> str:
    def find(node, target, path):
        if node is None:
            return False
        if node.val == target:
            return True
        path.append("L")
        if find(node.left, target, path):
            return True
        path[-1] = "R"
        if find(node.right, target, path):
            return True
        path.pop()
        return False

    ps, pd = [], []
    find(root, startValue, ps)
    find(root, destValue, pd)
    k = 0
    while k < len(ps) and k < len(pd) and ps[k] == pd[k]:
        k += 1
    return "U" * (len(ps) - k) + "".join(pd[k:])

Java

public static String getDirections(TreeNode root, int startValue, int destValue) {
    StringBuilder ps = new StringBuilder(), pd = new StringBuilder();
    findPath(root, startValue, ps);
    findPath(root, destValue, pd);
    int k = 0;
    while (k < ps.length() && k < pd.length() && ps.charAt(k) == pd.charAt(k)) k++;
    StringBuilder out = new StringBuilder();
    for (int i = k; i < ps.length(); i++) out.append('U');
    out.append(pd, k, pd.length());
    return out.toString();
}

static boolean findPath(TreeNode node, int target, StringBuilder path) {
    if (node == null) return false;
    if (node.val == target) return true;
    path.append('L');
    if (findPath(node.left, target, path)) return true;
    path.setCharAt(path.length() - 1, 'R');
    if (findPath(node.right, target, path)) return true;
    path.deleteCharAt(path.length() - 1);
    return false;
}

C++

bool findPath(TreeNode* node, int target, string& path);

string getDirections(TreeNode* root, int startValue, int destValue) {
    string ps, pd;
    findPath(root, startValue, ps);
    findPath(root, destValue, pd);
    size_t k = 0;
    while (k < ps.size() && k < pd.size() && ps[k] == pd[k]) k++;
    return string(ps.size() - k, 'U') + pd.substr(k);
}

bool findPath(TreeNode* node, int target, string& path) {
    if (!node) return false;
    if (node->val == target) return true;
    path.push_back('L');
    if (findPath(node->left, target, path)) return true;
    path.back() = 'R';
    if (findPath(node->right, target, path)) return true;
    path.pop_back();
    return false;
}

JavaScript

var getDirections = function(root, startValue, destValue) {
    var ps = [], pd = [];
    findPath(root, startValue, ps);
    findPath(root, destValue, pd);
    var k = 0;
    while (k < ps.length && k < pd.length && ps[k] === pd[k]) k++;
    var out = [];
    for (var i = k; i < ps.length; i++) out.push("U");
    for (var j = k; j < pd.length; j++) out.push(pd[j]);
    return out.join("");
};

var findPath = function(node, target, path) {
    if (node === null) return false;
    if (node.val === target) return true;
    path.push("L");
    if (findPath(node.left, target, path)) return true;
    path[path.length - 1] = "R";
    if (findPath(node.right, target, path)) return true;
    path.pop();
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Depth-First Search (DFS)