Step By Step Directions From a Binary Tree Node to Another
Understanding the Problem
We have a binary tree and two node values. We need to find directions to walk from the start node to the destination node. In a binary tree, you can only move to children (left or right) or back up to a parent. So the path between any two nodes must go up from the start to some ancestor, then down to the destination.
That ancestor is the Lowest Common Ancestor (LCA) of the two nodes. Any path from start to destination in a binary tree must pass through the LCA, because the LCA is the deepest node that sits above both of them. The path from start to LCA is all 'U' moves (going up), and the path from LCA to destination is 'L' and 'R' moves (going down).
There is no need to build an explicit graph and run BFS. We can find the LCA and construct the path directly using DFS.
Key Constraints:
2 <= n <= 10^5→ We need O(n) time. A quadratic approach that repeatedly scans the tree would be too slow.All values are unique→ We can identify nodes by their values without ambiguity, so matching a node tostartValueordestValueis exact.1 <= Node.val <= n→ Values are dense integers, so an array indexed by value can replace a hash map if memory matters.
Approach 1: BFS with Parent Pointers
Intuition
In a general graph, the shortest path between two nodes comes from BFS. A binary tree is a graph, with one missing piece: nodes point to their children but not to their parents. Add parent pointers and the problem becomes ordinary BFS. First traverse the tree to record each node's parent, then run BFS from the start node, treating left child, right child, and parent as the three neighbors of every node.
During BFS, we track the direction taken to reach each node ('L', 'R', or 'U') along with the node we came from. When BFS reaches the destination, we walk that trail backward to rebuild the path.
This converts the tree into an undirected graph and runs a full BFS, which costs more memory than the later approaches. It is a useful baseline because the correctness comes directly from the BFS shortest-path guarantee rather than any tree-specific reasoning.
Algorithm
- Traverse the tree (DFS or BFS) and store the parent of every node in a hash map. Also locate the actual start node reference.
- Run BFS from the start node. At each step, try three neighbors: left child (direction 'L'), right child (direction 'R'), and parent (direction 'U').
- Use a visited set to avoid revisiting nodes.
- When BFS reaches the destination node, reconstruct the path using the stored directions.
Example Walkthrough
Input:
First, the parent map records each node's parent: 1→5, 2→5, 3→1, 6→2, 4→2, and 5→null. BFS then starts from node 3.
The visited map stores, for each node reached, the node we came from and the direction taken. It begins as {3: (start, none)}.
- Pop 3. Its children are 3.left (which is null) and no right child, so only its parent 1 is unvisited. Record
visited[1] = (3, 'U')and enqueue 1. - Pop 1. Its left child 3 is already visited and it has no right child, so visit its parent 5. Record
visited[5] = (1, 'U')and enqueue 5. - Pop 5. Its left child 1 is visited, its right child 2 is new, and it has no parent. Record
visited[2] = (5, 'R')and enqueue 2. - Pop 2. Its left child 6 and right child 4 are both new, and its parent 5 is visited. Record
visited[6] = (2, 'L')andvisited[4] = (2, 'R'), enqueue both. - Pop 6. This is the destination.
Now reconstruct by following the trail backward from 6: 6 came from 2 via 'L', 2 came from 5 via 'R', 5 came from 1 via 'U', 1 came from 3 via 'U', and 3 is the start. Collected in reverse order this is "LRUU", so reversing gives "UURL".
Code
- Time Complexity: O(n). Building the parent map visits every node once. BFS visits every node at most once. Path reconstruction is at most O(n). Total: O(n).
- Space Complexity: O(n). The parent map, BFS queue, and visited map each store up to n entries.
BFS requires three auxiliary structures: a parent map, a visited map, and a queue. The next approach drops all of them by working with root-to-node paths instead.
Approach 2: Root-to-Node Paths with Common Prefix Removal
Intuition
The path from start to destination always goes through the Lowest Common Ancestor (LCA). The path from the root to start and the path from the root to destination share a common prefix: the portion from the root down to the LCA. After the LCA, the two paths diverge.
This gives the algorithm: find both root-to-node paths, strip their common prefix, replace the remaining start path with 'U' moves (going up to the LCA), and append the remaining destination path (going down from the LCA). The LCA itself is never computed as a node; it is the point where the prefixes stop matching, so the prefix length alone is enough.
Algorithm
- Use DFS to find the path from root to the start node, recording 'L' or 'R' at each step.
- Use DFS to find the path from root to the destination node, same way.
- Find the length of the common prefix between the two paths.
- Build the result: repeat 'U' for the remaining length of the start path, then append the remaining portion of the destination path.
Example Walkthrough
Code
- Time Complexity: O(n). Each DFS visits at most n nodes. The common prefix comparison and result building are each at most O(n). Total: O(n).
- Space Complexity: O(n). The DFS recursion stack can go up to O(n) deep for a skewed tree. The two path strings together are at most O(n).
This approach builds full paths from the root, then discards the common prefix as wasted work. The next approach finds the LCA first and builds each path starting from it, so nothing is thrown away.
Approach 3: LCA Then Build Paths
Intuition
This approach computes the LCA as an actual node first, then builds paths from the LCA to each target. Finding the LCA of two nodes in a binary tree is a standard recursion: if the current node is one of the targets, return it; otherwise search both subtrees; if both subtrees return non-null, the targets lie on opposite sides, so the current node is the LCA.
With the LCA in hand, one DFS from it to the start node gives the depth (the number of 'U' moves), and one DFS from it to the destination node gives the 'L'/'R' directions. The problem splits cleanly into two named subproblems: find the LCA, then build paths from it.
Algorithm
- Find the LCA of
startValueanddestValueusing the standard recursive LCA algorithm. - DFS from the LCA to find the path to
startValue. We only need the depth (number of steps), since all moves going up are 'U'. - DFS from the LCA to find the path to
destValue, recording 'L' and 'R' at each step. - Build the result: repeat 'U' for the depth to start, then append the direction path to destination.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Finding the LCA visits each node at most once. Finding paths from the LCA visits nodes in the LCA's subtree. Total: O(n).
- Space Complexity: O(n). The recursion stack for each DFS can go up to O(n) deep for a skewed tree. The path strings are at most O(n) long.