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

Problem

Given a binary tree and two node values, find the shortest path from the start node to the destination node. The path is expressed as a string of moves: 'L' (go left to a child), 'R' (go right to a child), and 'U' (go up to the parent).

[5,1,2,3,null,6,4]

• Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
• Output: "UURL"
• Explanation: From node 3, go up to 1 (U), up to 5 (U), right to 2 (R), left to 6 (L)

A counter-example clarifies the direction encoding: if startValue = 1 and destValue = 3, the output is just "L" — one step down to the left child, no upward moves needed.

Intuition

Every path from one node to another in a binary tree passes through their Lowest Common Ancestor (LCA). The path goes up from the start to the LCA, then down from the LCA to the destination. If you record the root-to-start and root-to-dest paths as strings of L/R moves, those two strings share a common prefix — that prefix is exactly the path to the LCA. Strip the shared prefix, replace the remaining start path with 'U' moves (one per step up), and concatenate the remaining dest path.

Solution — Root Paths + LCA Strip

Find the path from the root to each target node using DFS, strip the common prefix to locate the LCA, then combine the upward and downward segments.

1. DFS from root to startValue, recording each 'L' or 'R' direction taken
2. DFS from root to destValue, recording each 'L' or 'R' direction taken
3. Walk both paths in parallel until they diverge — the divergence point is the LCA
4. The remaining start-path characters all become 'U' moves (one per level up)
5. Return that 'U' sequence concatenated with the remaining dest-path characters

1class Solution:
2    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
3        def find_path(node, target, path):
4            if node is None:
5                return False
6            if node.val == target:
7                return True
8            path.append('L')
9            if find_path(node.left, target, path):
10                return True
11            path.pop()  # left subtree failed, backtrack before trying right
12            path.append('R')
13            if find_path(node.right, target, path):
14                return True
15            path.pop()  # right subtree failed, backtrack to caller
16            return False
17
18        start_path, dest_path = [], []
19        find_path(root, startValue, start_path)
20        find_path(root, destValue, dest_path)
21
22        # The common prefix is the path to the LCA — strip it from both
23        prefix_len = 0
24        while (prefix_len < len(start_path) and prefix_len < len(dest_path)
25               and start_path[prefix_len] == dest_path[prefix_len]):
26            prefix_len += 1
27
28        up_steps = len(start_path) - prefix_len  # steps from start up to LCA
29        return 'U' * up_steps + ''.join(dest_path[prefix_len:])

Time: O(n) — two independent DFS traversals each visit at most every node once

Space: O(n) — the recursion stack and path strings are both bounded by tree height, which is O(n) in the worst case

Complexity Summary

Common Mistakes

• Replacing the entire start path with 'U' moves — only the portion after the LCA should become 'U's; using len(startPath) steps up overshoots past the LCA and gives a wrong answer
• Forgetting to pop before trying the other child — if the left DFS fails, you must remove the 'L' you appended before appending 'R'; skipping the pop leaves stale characters that corrupt both paths
• Off-by-one on prefix length — the comparison loop correctly stops at the first mismatch; using <= instead of < in the while condition will include the divergence character and strip one direction from the dest path
• Using len(startPath) instead of len(startPath) - prefixLen for up-count — when start is a descendant of the LCA (e.g., start is an ancestor of dest), the prefix covers the entire start path and up_steps should be 0
• Trying to find both nodes in a single DFS pass — it's tempting but error-prone; two separate calls are cleaner and still O(n) total

Related Problems

• lowest-common-ancestor-of-a-binary-tree — the LCA is the conceptual hinge this entire approach turns on
• all-nodes-distance-k-in-binary-tree — same class of problem: distances and paths in a tree that require upward traversal
• sum-root-to-leaf-numbers — uses the same DFS path-recording pattern to accumulate root-to-leaf information
• path-sum-ii — also collects full root-to-node paths via backtracking DFS
• binary-tree-right-side-view — tree traversal that tracks structural position, a complementary pattern to path recording