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

Medium Trees & BST LCA Original on LeetCode

Step-By-Step Directions From a Binary Tree Node to Another is a medium trees & bst problem solved with the lca pattern. The best approach, optimal (root paths + common prefix), runs in O(n) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (parent map + bfs) up.

Problem

You are given the root of a binary tree with n nodes, each holding a distinct value from 1 to n, and two values startValue and destValue.

Return the shortest sequence of moves that leads from the node with value startValue to the node with value destValue, as a string made of these 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.

Examples

Example 1

Input
root = [5, 4, 6, 2, 7, null, 1, null, null, 3], startValue = 3, destValue = 1
Output
"UUURR"
Why
From 3 go up to 7, up to 4, up to the root 5, then right to 6 and right again to 1.

Example 2

Input
root = [2, 3, 1], startValue = 2, destValue = 3
Output
"L"
Why
The destination is the left child of the start.

Example 3

Input
root = [1, 2, null, 3, 4], startValue = 4, destValue = 3
Output
"UL"
Why
Go up from 4 to their common parent 2, then down to its left child 3.

Constraints

  • The number of nodes n is in the range [2, 10^5]
  • 1 <= Node.val <= n, and all values are distinct
  • startValue and destValue are values of nodes in the tree
  • startValue != destValue

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (parent map + BFS)O(n)O(n)
Optimal (root paths + common prefix)O(n)O(h)

1Brute force (parent map + BFS)

TimeO(n)Each node is visited a constant number of times by the parent pass and the BFS.
SpaceO(n)Parent map, visited map and queue each hold up to n nodes. It needs several extra maps, which the optimal approach avoids.

Treat the tree as an undirected graph. Record each node's parent, then run a BFS from the start node, moving to the left child ('L'), right child ('R') or parent ('U'). Remember how each node was first reached, and rebuild the direction string once the destination is popped.

  1. DFS/BFS from the root to record every node's parent and find the start node.
  2. BFS from the start; for each neighbour (left, right, parent) not yet seen, store (previous node, letter).
  3. When the destination is reached, walk the stored links back to the start, collecting letters.
  4. Reverse the letters and return them as a string.
class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        TreeNode start = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.val == startValue) start = node;
            if (node.left != null) { parent.put(node.left, node); stack.push(node.left); }
            if (node.right != null) { parent.put(node.right, node); stack.push(node.right); }
        }
        Map<TreeNode, TreeNode> from = new HashMap<>();
        Map<TreeNode, Character> step = new HashMap<>();
        from.put(start, null);
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(start);
        TreeNode dest = null;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == destValue) { dest = node; break; }
            TreeNode[] next = { node.left, node.right, parent.get(node) };
            char[] letter = { 'L', 'R', 'U' };
            for (int k = 0; k < 3; k++) {
                if (next[k] != null && !from.containsKey(next[k])) {
                    from.put(next[k], node);
                    step.put(next[k], letter[k]);
                    queue.add(next[k]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (TreeNode cur = dest; cur != start; cur = from.get(cur)) sb.append(step.get(cur));
        return sb.reverse().toString();
    }
}

2Optimal (root paths + common prefix)

TimeO(n)Each DFS visits every node at most once.
SpaceO(h)The recursion stack and the path strings are bounded by the tree height h (up to n for a skewed tree).

Record the path from the root to the start and from the root to the destination as strings of 'L' and 'R'. Their longest common prefix leads to the lowest common ancestor. Everything after that prefix on the start's path has to be climbed back up (one 'U' per letter), and everything after it on the destination's path is followed as-is.

  1. Find the root-to-start path and the root-to-destination path with a DFS that appends a letter going down and removes it when backtracking.
  2. Skip the common prefix of the two paths (length p).
  3. Answer = 'U' repeated (startPath.length - p) times + destPath.substring(p).
class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder toStart = new StringBuilder(), toDest = new StringBuilder();
        findPath(root, startValue, toStart);
        findPath(root, destValue, toDest);
        int p = 0;
        while (p < toStart.length() && p < toDest.length() && toStart.charAt(p) == toDest.charAt(p)) p++;
        StringBuilder sb = new StringBuilder();
        for (int i = p; i < toStart.length(); i++) sb.append('U');
        sb.append(toDest, p, toDest.length());
        return sb.toString();
    }

    private 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;
    }
}

Edge cases to test

  • The destination is a descendant of the start (no 'U' at all)
  • The start is a descendant of the destination (only 'U's)
  • The two nodes are in different subtrees of the root
  • A very deep, skewed tree

Hints

Hint 1

Any shortest path in a tree goes up from the start to the lowest common ancestor, then down to the destination.

Hint 2

Write down the root-to-node path (as 'L'/'R' letters) for both nodes. What does their common prefix represent?

Hint 3

Drop the common prefix; every remaining step on the start's path becomes 'U', followed by the rest of the destination's path.

FAQ

What is the best time complexity for Step-By-Step Directions From a Binary Tree Node to Another?

Optimal (root paths + common prefix) runs in O(n) time and O(h) extra space. Each DFS visits every node at most once.

Which pattern does Step-By-Step Directions From a Binary Tree Node to Another use?

It is a trees & bst problem that uses the lca pattern. Other problems with the same pattern: Lowest Common Ancestor of a Binary Tree, Lowest Common Ancestor of a Binary Search Tree, Smallest Common Region.

Is there a brute force solution for Step-By-Step Directions From a Binary Tree Node to Another?

Yes. Brute force (parent map + BFS) takes O(n) time and O(n) space. Treat the tree as an undirected graph.

Which edge cases should I test for Step-By-Step Directions From a Binary Tree Node to Another?

The destination is a descendant of the start (no 'U' at all); The start is a descendant of the destination (only 'U's); The two nodes are in different subtrees of the root; A very deep, skewed tree.