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.
This approach involves finding the path from the start node to the root and the destination node to the root. Using these paths, the Lowest Common Ancestor (LCA) of the start and destination nodes is determined. This allows us to break down the path from start to destination as moving up towards the root to the LCA, then down towards the destination. Once these steps are identified, we can replace moves with correct directions ('L', 'R', 'U').
The code defines a TreeNode class with a method get_directions that computes the shortest path between two nodes in the form of directions. It uses a helper function path_to_node to traverse from the root to the specific node, appending 'L' or 'R' to a path list and returning True when the node is found. The main function finds paths to both start and destination nodes and calculates the direction by comparing the path steps. The paths are adjusted to determine when to move up and the remaining path to take.
Time Complexity: O(n), where n is the number of nodes, as each node could be traversed in the worst-case.
Space Complexity: O(h), where h is the height of the tree due to recursion stack and storing paths.
This approach uses a DFS to build a parent map of nodes first. With this map, we can easily track the movement from any node to any other node. We then extract paths from startValue and destValue up to a common ancestor. The directions are computed through knowledge of parent-child relationships and mapped accordingly using 'L', 'R', and 'U'.
This solution creates a map of parent nodes using a depth-first search traversal. Once the parent map is available, the method accumulates paths from start and destination nodes to the root by tracking their parent relationships. Both paths are assessed for shared parent nodes to identify the LCA depth. The excess upward steps in the start path are marked with 'U', and further navigation from the LCA to the destination is indicated by the recorded 'L'/'R' movements.
Python
JavaScript
C#
Time Complexity: O(n), traversing all nodes for setup. Space Complexity: O(n) due to the parent mapping.
We can first find the lowest common ancestor of nodes startValue and destValue, denoted as node. Then, starting from node, we find the paths to startValue and destValue respectively. The path from startValue to node will consist of a number of Us, and the path from node to destValue will be the path. Finally, we concatenate these two paths.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
JavaScript
We can start from root, find the paths to startValue and destValue, denoted as pathToStart and pathToDest, respectively. Then, remove the longest common prefix of pathToStart and pathToDest. At this point, the length of pathToStart is the number of Us in the answer, and the path of pathToDest is the path in the answer. We just need to concatenate these two paths.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Find Paths to Root and Compute Directions | Time Complexity: O(n), where n is the number of nodes, as each node could be traversed in the worst-case. |
| Using Depth-First Search (DFS) to Build Parent Map | Time Complexity: O(n), traversing all nodes for setup. Space Complexity: O(n) due to the parent mapping. |
| Lowest Common Ancestor + DFS | — |
| Lowest Common Ancestor + DFS (Optimized) | — |
| 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. |
Step-By-Step Directions from a Binary Tree Node to Another - Leetcode 2096 - Python • NeetCodeIO • 15,032 views views
Watch 9 more video solutions →Practice Step-By-Step Directions From a Binary Tree Node to Another with our built-in code editor and test cases.
Practice on FleetCode