Step-By-Step Directions From a Binary Tree Node to Another
MedPrompt
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:
- The number of nodes in the tree is
n. 2 <= n <= 1051 <= Node.val <= n- All the values in the tree are unique.
1 <= startValue, destValue <= nstartValue != destValue
Approaches
3 approaches with complexity analysis and trade-offs.
This approach transforms the binary tree into a general graph and then applies a standard shortest path algorithm, Breadth-First Search (BFS). Since we need to travel upwards ('U'), the graph must include edges from children to parents. This is achieved by first building a map to store parent pointers for each node.
Algorithm
- Build Parent Map: Traverse the tree using a level-order traversal (BFS) to populate a
Map<TreeNode, TreeNode>that stores the parent of each node. During this traversal, also find theTreeNodeobject corresponding to thestartValue. - Perform BFS for Shortest Path: Start a Breadth-First Search (BFS) from the
startNode. - Queue State: The BFS queue will store pairs of
(TreeNode, path_string), representing the current node and the path taken to reach it. - Track Visited Nodes: Use a
Set<TreeNode>to keep track of visited nodes to prevent cycles (e.g., moving from a child to parent and back) and avoid redundant computations. - Explore Neighbors: In each step of the BFS, for the current node, explore its three potential neighbors: its parent (from the map), its left child, and its right child.
- Path Construction: For each valid, unvisited neighbor, append the corresponding direction ('U', 'L', or 'R') to the current path string and enqueue the neighbor along with the new path.
- Termination: BFS naturally finds the shortest path in an unweighted graph. Therefore, the first time the
destNodeis reached, the path associated with it is the shortest. Return this path immediately.
Walkthrough
- Build Parent Map: First, we traverse the entire tree to build a data structure, typically a
HashMap, that maps each node to its parent. This allows us to navigate upwards from any node. While building this map, we can also locate the reference to thestartNode. - Perform BFS: With the parent pointers available, the tree can be treated as a graph. We initiate a BFS starting from the
startNode. The queue used for BFS will store not just the nodes to visit, but also the path string of directions taken to reach that node from thestartNode. - Exploration and Path Finding: In each iteration of the BFS, we dequeue a node and its path. If this node is the destination, we have found the shortest path and can return the associated path string. Otherwise, we explore its neighbors: the parent (using our map), the left child, and the right child. For each unvisited neighbor, we form the new path by appending the correct direction ('U', 'L', or 'R') and add it to the queue and a
visitedset.
// Definition for a binary tree node.// public class TreeNode {// int val;// TreeNode left;// TreeNode right;// TreeNode() {}// TreeNode(int val) { this.val = val; }// TreeNode(int val, TreeNode left, TreeNode right) {// this.val = val;// this.left = left;// this.right = right;// }// } // A simple Pair class to use in the queueclass Pair<K, V> { private K key; private V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; }} class Solution { public String getDirections(TreeNode root, int startValue, int destValue) { Map<TreeNode, TreeNode> parentMap = new HashMap<>(); TreeNode startNode = findStartNodeAndBuildParentMap(root, startValue, parentMap); Queue<Pair<TreeNode, String>> queue = new LinkedList<>(); queue.offer(new Pair<>(startNode, "")); Set<TreeNode> visited = new HashSet<>(); visited.add(startNode); while (!queue.isEmpty()) { Pair<TreeNode, String> current = queue.poll(); TreeNode currentNode = current.getKey(); String currentPath = current.getValue(); if (currentNode.val == destValue) { return currentPath; } // Move Up (to parent) TreeNode parent = parentMap.get(currentNode); if (parent != null && !visited.contains(parent)) { visited.add(parent); queue.offer(new Pair<>(parent, currentPath + "U")); } // Move Left if (currentNode.left != null && !visited.contains(currentNode.left)) { visited.add(currentNode.left); queue.offer(new Pair<>(currentNode.left, currentPath + "L")); } // Move Right if (currentNode.right != null && !visited.contains(currentNode.right)) { visited.add(currentNode.right); queue.offer(new Pair<>(currentNode.right, currentPath + "R")); } } return ""; // Should not be reached given the problem constraints } private TreeNode findStartNodeAndBuildParentMap(TreeNode node, int startValue, Map<TreeNode, TreeNode> parentMap) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(node); TreeNode startNode = null; while (!queue.isEmpty()) { TreeNode current = queue.poll(); if (current.val == startValue) { startNode = current; } if (current.left != null) { parentMap.put(current.left, current); queue.offer(current.left); } if (current.right != null) { parentMap.put(current.right, current); queue.offer(current.right); } } return startNode; }}Complexity
Time
O(N), where N is the number of nodes. The initial traversal to build the parent map takes O(N). The subsequent BFS also visits each node and edge at most once, which also takes O(N) time.
Space
O(N), where N is the number of nodes in the tree. The `parentMap` can store up to N-1 entries. In the worst-case scenario, the BFS `queue` and `visited` set can also store up to O(N) nodes.
Trade-offs
Pros
It is a general and robust approach for finding the shortest path in any graph, not just trees.
The correctness is guaranteed by the properties of Breadth-First Search for unweighted graphs.
Cons
Requires significant extra space (O(N)) to store the parent map, the BFS queue, and the visited set.
The implementation is more involved compared to solutions that work directly on the tree structure.
Has higher constant factors for time and space compared to more optimized tree-specific approaches.
This approach avoids building an explicit graph. Instead, it finds the path from the root to the start node and the path from the root to the destination node using two separate traversals. The shortest path between the two nodes must pass through their Lowest Common Ancestor (LCA). By comparing the two root-to-node paths, we can identify the LCA, trim the common path segment, and then construct the final directions.
Algorithm
- Find Path to Start: Implement a recursive DFS helper function,
findPath(node, target, path), that traverses the tree to find thetargetvalue. The function builds the path (a sequence of 'L' and 'R') in aStringBuilderand returnstrueonce the target is found. - Find Path to Destination: Call the
findPathfunction once to get the path from the root to thestartValue(pathToStart). - Second Traversal: Call the
findPathfunction a second time to get the path from the root to thedestValue(pathToDest). - Find Common Prefix (LCA): Iterate through both
pathToStartandpathToDestto find the length of their longest common prefix. The node at the end of this common path is the Lowest Common Ancestor (LCA). - Construct Final Path:
- The path from the start node up to the LCA consists of 'U' moves. The number of 'U's is
pathToStart.length() - commonPrefixLength. - The path from the LCA down to the destination node is the non-common part of
pathToDest, which ispathToDest.substring(commonPrefixLength). - Concatenate these two parts to form the final result.
- The path from the start node up to the LCA consists of 'U' moves. The number of 'U's is
Walkthrough
The core idea is that the path from any node A to node B can be seen as moving from A up to their Lowest Common Ancestor (LCA), and then down to B. We can find the paths from the root to both the start and destination nodes. The common part of these paths leads to the LCA.
- Find Paths from Root: We perform two separate Depth-First Searches (DFS) from the root. The first DFS finds the path to
startValue, and the second finds the path todestValue. Each DFS records the sequence of 'L' (left) and 'R' (right) moves in a string. - Process Paths: After obtaining the two path strings, we find their common prefix. For example, if
pathToStartis "RLR" andpathToDestis "RLL", the common prefix is "RL". This means the LCA is reached by taking the path "RL" from the root. - Generate Directions: The path from the start node to the LCA is the reverse of the unique part of
pathToStart, which translates to a series of 'U' (up) moves. The path from the LCA to the destination is simply the unique part ofpathToDest. The final direction string is the concatenation of these two parts.
class Solution { public String getDirections(TreeNode root, int startValue, int destValue) { StringBuilder pathToStart = new StringBuilder(); StringBuilder pathToDest = new StringBuilder(); // First traversal to find path to startValue findPath(root, startValue, pathToStart); // Second traversal to find path to destValue findPath(root, destValue, pathToDest); int i = 0; // Find the length of the common prefix (path to LCA) while (i < pathToStart.length() && i < pathToDest.length() && pathToStart.charAt(i) == pathToDest.charAt(i)) { i++; } StringBuilder result = new StringBuilder(); // Add 'U' for each step from start to LCA for (int j = 0; j < pathToStart.length() - i; j++) { result.append('U'); } // Add steps from LCA to destination result.append(pathToDest.substring(i)); return result.toString(); } private boolean findPath(TreeNode node, int target, StringBuilder path) { if (node == null) { return false; } if (node.val == target) { return true; } path.append('L'); if (findPath(node.left, target, path)) { return true; } path.deleteCharAt(path.length() - 1); // Backtrack path.append('R'); if (findPath(node.right, target, path)) { return true; } path.deleteCharAt(path.length() - 1); // Backtrack return false; }}Complexity
Time
O(N), where N is the number of nodes. In the worst case, each of the two `findPath` calls might traverse the entire tree. Thus, the total time is O(N) + O(N) = O(N).
Space
O(H), where H is the height of the tree. This space is consumed by the recursion stack for DFS and the `StringBuilder`s used to store the paths. In the worst case of a skewed tree, H can be equal to N, making the space complexity O(N).
Trade-offs
Pros
Simpler to implement than the graph conversion approach as it works directly with the tree structure.
Does not require building large auxiliary data structures like a parent map for the entire tree.
Cons
This approach is inefficient because it traverses the tree twice. Many nodes might be visited in both the first and second traversals, leading to redundant computations.
This is the most efficient approach. It improves upon the two-traversal method by finding the paths from the root to both the start and destination nodes in a single DFS traversal, thus avoiding redundant work. After finding both paths, it identifies the common prefix (representing the path to the LCA) and constructs the final directions.
Algorithm
- Single DFS Traversal: Create a single recursive DFS function,
findPaths(node, startVal, destVal, currentPath, ...). - Path Discovery: This function traverses the tree from the root. It maintains a
currentPathfrom the root to the current node. When it encountersstartVal, it saves a copy ofcurrentPathaspathToStart. Similarly, when it findsdestVal, it saves the path aspathToDest. - Optimization: The traversal can be pruned. Once both
pathToStartandpathToDesthave been found, the recursion can stop exploring further branches. - Process Paths: After the single traversal completes, we will have both path strings. The rest of the logic is identical to the previous approach:
- Find the length of the common prefix
i. - Generate
pathToStart.length() - i'U' moves. - Append
pathToDest.substring(i). - Return the combined string.
- Find the length of the common prefix
Walkthrough
This approach refines the previous one by merging the two separate DFS traversals into one. A single pass over the tree is sufficient to find the paths to both the start and destination nodes.
- Single Traversal: We design a DFS function that searches for both
startValueanddestValuesimultaneously. This function keeps track of the path from the root to the current node. When either target node is found, its corresponding path from the root is recorded. We can use class member variables to store the two paths once they are found. - Path Processing: Once the traversal is complete (or as soon as both paths are found), the procedure is the same as in the two-traversal approach. We find the longest common prefix of the two paths. This prefix corresponds to the path from the root to the LCA.
- Direction Generation: The directions are then constructed by first generating 'U's for every step in the non-common part of the start path, and then appending the non-common part of the destination path.
class Solution { private StringBuilder pathToStart = null, pathToDest = null; public String getDirections(TreeNode root, int startValue, int destValue) { // Find both paths in a single traversal findPaths(root, startValue, destValue, new StringBuilder()); int i = 0; // Find the length of the common prefix while (i < pathToStart.length() && i < pathToDest.length() && pathToStart.charAt(i) == pathToDest.charAt(i)) { i++; } StringBuilder result = new StringBuilder(); // Append 'U' for the path from start to LCA for (int j = 0; j < pathToStart.length() - i; j++) { result.append('U'); } // Append the path from LCA to destination result.append(pathToDest.substring(i)); return result.toString(); } private void findPaths(TreeNode node, int startVal, int destVal, StringBuilder currentPath) { // Base case or if both paths are already found if (node == null || (pathToStart != null && pathToDest != null)) { return; } if (node.val == startVal) { pathToStart = new StringBuilder(currentPath); } if (node.val == destVal) { pathToDest = new StringBuilder(currentPath); } // Explore left subtree currentPath.append('L'); findPaths(node.left, startVal, destVal, currentPath); currentPath.deleteCharAt(currentPath.length() - 1); // Backtrack // Optimization: if both found, no need to check right subtree if (pathToStart == null || pathToDest == null) { // Explore right subtree currentPath.append('R'); findPaths(node.right, startVal, destVal, currentPath); currentPath.deleteCharAt(currentPath.length() - 1); // Backtrack } }}Complexity
Time
O(N). The tree is traversed only once. The subsequent path comparison and string building operations take O(H) time, where H is the tree height (at most N). The overall time complexity is dominated by the single traversal.
Space
O(H), where H is the height of the tree. This space is for the recursion stack and the path `StringBuilder`s. In the worst case of a skewed tree, H can be N, leading to O(N) space complexity.
Trade-offs
Pros
Most time-efficient approach as it traverses the tree only once, minimizing redundant node visits.
Avoids the overhead of creating explicit graph structures like parent maps.
Cleanly separates the path-finding logic from the direction-generation logic.
Cons
The recursive function signature can be slightly more complex due to the need to pass around multiple path builders or use class members to store the results.
While asymptotically optimal, it still requires O(N) space for the recursion stack and path strings in the worst case of a skewed tree.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < Integer , List < List < String >>> edges ; private Set < Integer > visited ; private String ans ; public String getDirections ( TreeNode root , int startValue , int destValue ) { edges = new HashMap <>(); visited = new HashSet <>(); ans = null ; traverse ( root ); dfs ( startValue , destValue , new ArrayList <>()); return ans ; } private void traverse ( TreeNode root ) { if ( root == null ) { return ; } if ( root . left != null ) { edges . computeIfAbsent ( root . val , k -> new ArrayList <>()) . add ( Arrays . asList ( String . valueOf ( root . left . val ), "L" )); edges . computeIfAbsent ( root . left . val , k -> new ArrayList <>()) . add ( Arrays . asList ( String . valueOf ( root . val ), "U" )); } if ( root . right != null ) { edges . computeIfAbsent ( root . val , k -> new ArrayList <>()) . add ( Arrays . asList ( String . valueOf ( root . right . val ), "R" )); edges . computeIfAbsent ( root . right . val , k -> new ArrayList <>()) . add ( Arrays . asList ( String . valueOf ( root . val ), "U" )); } traverse ( root . left ); traverse ( root . right ); } private void dfs ( int start , int dest , List < String > t ) { if ( visited . contains ( start )) { return ; } if ( start == dest ) { if ( ans == null || ans . length () > t . size ()) { ans = String . join ( "" , t ); } return ; } visited . add ( start ); if ( edges . containsKey ( start )) { for ( List < String > item : edges . get ( start )) { t . add ( item . get ( 1 )); dfs ( Integer . parseInt ( item . get ( 0 )), dest , t ); t . remove ( t . size () - 1 ); } } } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} startValue * @param {number} destValue * @return {string} */ var getDirections = function (root, startValue, destValue) { const lca = (node, p, q) => { if (node === null || [p, q].includes(node.val)) { return node; } const left = lca(node.left, p, q); const right = lca(node.right, p, q); return left && right ? node : (left ?? right); }; const dfs = (node, x, path) => { if (node === null) { return false; } if (node.val === x) { return true; } path.push(" L "); if (dfs(node.left, x, path)) { return true; } path[path.length - 1] = " R "; if (dfs(node.right, x, path)) { return true; } path.pop(); return false; }; const node = lca(root, startValue, destValue); const pathToStart = []; const pathToDest = []; dfs(node, startValue, pathToStart); dfs(node, destValue, pathToDest); return " U ".repeat(pathToStart.length) + pathToDest.join(""); };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: unordered_map < int , vector < pair < int , char >>> edges ; unordered_set < int > visited ; string ans ; string getDirections ( TreeNode * root , int startValue , int destValue ) { ans = "" ; traverse ( root ); string t = "" ; dfs ( startValue , destValue , t ); return ans ; } void traverse ( TreeNode * root ) { if ( ! root ) return ; if ( root -> left ) { edges [ root -> val ]. push_back ({ root -> left -> val , 'L' }); edges [ root -> left -> val ]. push_back ({ root -> val , 'U' }); } if ( root -> right ) { edges [ root -> val ]. push_back ({ root -> right -> val , 'R' }); edges [ root -> right -> val ]. push_back ({ root -> val , 'U' }); } traverse ( root -> left ); traverse ( root -> right ); } void dfs ( int start , int dest , string & t ) { if ( visited . count ( start )) return ; if ( start == dest ) { if ( ans == "" || ans . size () > t . size ()) ans = t ; return ; } visited . insert ( start ); if ( edges . count ( start )) { for ( auto & item : edges [ start ]) { t += item . second ; dfs ( item . first , dest , t ); t . pop_back (); } } } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def getDirections ( self , root : Optional [ TreeNode ], startValue : int , destValue : int ) -> str : edges = defaultdict ( list ) ans = None visited = set () def traverse ( root ): if not root : return if root . left : edges [ root . val ]. append ([ root . left . val , 'L' ]) edges [ root . left . val ]. append ([ root . val , 'U' ]) if root . right : edges [ root . val ]. append ([ root . right . val , 'R' ]) edges [ root . right . val ]. append ([ root . val , 'U' ]) traverse ( root . left ) traverse ( root . right ) def dfs ( start , dest , t ): nonlocal ans if start in visited : return if start == dest : if ans is None or len ( ans ) > len ( t ): ans = '' . join ( t ) return visited . add ( start ) for d , k in edges [ start ]: t . append ( k ) dfs ( d , dest , t ) t . pop () traverse ( root ) dfs ( startValue , destValue , []) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.