Step-By-Step Directions in a Binary Tree — LC 2096 LCA + Path Build

Problem Statement#

Given the root of a binary tree with unique values and two integers startValue and destValue, return the shortest path between two nodes as a string of moves: 'L' (go to left child), 'R' (go to right child), 'U' (go to parent).

Constraints:

• The number of nodes is in the range [2, 10^5]
• 1 <= Node.val <= n
• All values are unique
• startValue and destValue exist and are different

Input:  root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"

Input:  root = [2,1], startValue = 2, destValue = 1
Output: "L"

Why This Problem Matters#

LeetCode 2096 Step-By-Step Directions From a Binary Tree Node to Another is a Medium-difficulty interview question asked at Amazon, Meta, Google, and Microsoft. It is a clean composite problem — combining LCA discovery, root-to-node path building, and string transformation — and tests whether candidates can compose primitives instead of reaching for a custom graph approach.

A frequent trap: candidates convert the tree to an undirected graph and run BFS. That works but masks understanding. The elegant approach exploits the tree-only fact that every two nodes share a unique LCA and the shortest path between them passes through it. This is the essence of "use the data structure's invariants" thinking that FAANG looks for.

The pattern recurs in any tree-pathing query: routing in a hierarchical org chart, navigating filesystem paths, and tracing inheritance chains in language tooling.

The Core Insight#

The shortest path from start to dest in a tree goes UP from start to the LCA and then DOWN from the LCA to dest. Equivalently:

1. Build path strings from root to start (call it s) and root to dest (call it d).
2. Strip the longest common prefix — that prefix is the path from root to LCA, and it cancels out.
3. Replace the remaining s (root-to-LCA-then-to-start, post-prefix) with U characters of equal length — those are the upward moves.
4. Append the remaining d (the downward-from-LCA-to-dest path).

This avoids explicitly finding the LCA node — the common-prefix step does it implicitly.

Visual Dry Run#

Tree: [5,1,2,3,null,6,4], start = 3, dest = 6.

        5
       / \
      1   2
     /   / \
    3   6   4

Path root -> 3: "LL" Path root -> 6: "RL"

Common prefix: "" (empty). So:

• s = "LL" -> replace with "UU" (two upward moves).
• d = "RL" -> append.

Result: "UU" + "RL" = "UURL".

Solution (Optimal)#

class Solution:
    def getDirections(self, root, startValue, destValue):
        def path(node, target, acc):
            if not node:
                return False
            if node.val == target:
                return True
            acc.append('L')
            if path(node.left, target, acc):
                return True
            acc.pop()
            acc.append('R')
            if path(node.right, target, acc):
                return True
            acc.pop()
            return False
 
        s, d = [], []
        path(root, startValue, s)
        path(root, destValue, d)
        # Strip common prefix
        i = 0
        while i < len(s) and i < len(d) and s[i] == d[i]:
            i += 1
        return 'U' * (len(s) - i) + ''.join(d[i:])

var getDirections = function(root, startValue, destValue) {
    const path = (node, target, acc) => {
        if (!node) return false;
        if (node.val === target) return true;
        acc.push('L');
        if (path(node.left, target, acc)) return true;
        acc.pop();
        acc.push('R');
        if (path(node.right, target, acc)) return true;
        acc.pop();
        return false;
    };
    const s = [], d = [];
    path(root, startValue, s);
    path(root, destValue, d);
    let i = 0;
    while (i < s.length && i < d.length && s[i] === d[i]) i++;
    return 'U'.repeat(s.length - i) + d.slice(i).join('');
};

Time: O(n) — two DFS passes, each visits O(n) nodes in the worst case. Space: O(n) for the two path lists plus recursion.

Common Mistakes#

• Building both paths in one DFS that aborts after finding both — the early exits get tangled.
• Reversing the start path manually — unnecessary; replacing every char with U works because all upward moves are identical.
• Forgetting acc.pop() between left and right tries — corrupts the path.
• Off-by-one when stripping the common prefix.
• Converting to a graph and running BFS — works but loses the tree-specific elegance.

Interview Tips#

• State the LCA insight explicitly: "Path goes up from start, through LCA, down to dest."
• Show the common-prefix trick on a small example before coding.
• Mention complexity: O(n) time and O(n) auxiliary path arrays.
• Edge cases: start is ancestor of dest (no Us); dest is ancestor of start (all Us + no descent).
• Discuss alternative: explicit LCA computation + two path traversals — same complexity, slightly more code.

Follow-up Questions#

• k-ary tree (not binary)? Same approach but path characters become child indices.
• Multiple queries? Precompute paths from root for every node once — O(n^2) preprocessing, O(L) per query.
• Find LCA explicitly? Once paths are built, walk forward until they diverge.
• Distance between two nodes? Sum of remaining s length and d length after common prefix removal.
• What if values are not unique? Use node references or unique ids instead.

Key Takeaways#

• LeetCode 2096 is a Medium-difficulty FAANG tree question asked at Amazon, Meta, and Google.
• The shortest path between two tree nodes goes up to LCA and then down to dest.
• Build root-to-node paths for both nodes; strip the common prefix; replace start's remainder with Us.
• No explicit LCA computation needed — the common-prefix trick handles it.
• Time complexity O(n) for path construction; space O(n) for path lists.
• Replacing every char with U works because all upward moves are indistinguishable.
• The pattern transfers to hierarchical navigation, org charts, and any tree-routing problem.