Watch 10 video solutions for Step-By-Step Directions From a Binary Tree Node to Another, a medium level problem involving String, Tree, Depth-First Search. This walkthrough by NeetCodeIO has 15,032 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.
Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:
'L' means to go from a node to its left child node.'R' means to go from a node to its right child node.'U' means to go from a node to its parent node.Return the step-by-step directions of the shortest path from node s to node t.
Example 1:
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6 Output: "UURL" Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.
Example 2:
Input: root = [2,1], startValue = 2, destValue = 1 Output: "L" Explanation: The shortest path is: 2 → 1.
Constraints:
n.2 <= n <= 1051 <= Node.val <= n1 <= startValue, destValue <= nstartValue != destValueProblem Overview: You are given a binary tree and two node values: startValue and destValue. The task is to return a string describing the directions to move from the start node to the destination node. Moves are encoded as L (left child), R (right child), and U (parent).
Approach 1: Find Paths to Root and Compute Directions (O(n) time, O(n) space)
This method finds the path from the root to both startValue and destValue using a DFS traversal. Each path records moves (L or R). Once both paths are found, iterate from the start of both arrays to locate the lowest common ancestor (LCA) where the paths diverge. For every remaining step in the start path, append U. Then append the remaining moves from the destination path. This approach works because the path from start to destination always goes up to the LCA and then down to the target. It relies heavily on recursive traversal of a binary tree using depth-first search.
Approach 2: Using Depth-First Search (DFS) to Build Parent Map (O(n) time, O(n) space)
Another strategy treats the tree like an undirected graph. Run a DFS to build a parent map for each node while also tracking whether the node is a left or right child. Once this structure is ready, perform a DFS or BFS starting from startValue. From any node you can move left, right, or up to the parent. Track visited nodes and accumulate direction characters (L, R, U) until destValue is reached. This approach is flexible because it converts the tree into a graph traversal problem and explores neighbors directly.
Recommended for interviews: The path comparison approach is typically expected. It clearly shows understanding of tree traversal and the concept of the lowest common ancestor. Building a parent map and exploring like a graph also works in O(n) time but uses a slightly heavier structure. Interviewers usually prefer the LCA-style path solution because the reasoning is simpler and the resulting code is shorter.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Find Paths to Root and Compute Directions | O(n) | O(n) | Best general solution. Clean logic using root-to-node paths and LCA comparison. |
| DFS Parent Map + Graph Traversal | O(n) | O(n) | Useful when treating the tree as an undirected graph with parent links. |