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 != destValueTo solve #2096 Step-By-Step Directions From a Binary Tree Node to Another, the key idea is to identify the relationship between the startValue and destValue nodes in the binary tree. A common strategy is to first locate their Lowest Common Ancestor (LCA). The LCA represents the node where the paths to both target nodes diverge.
Using Depth-First Search (DFS), you can find the path from the root to each node and then determine the LCA by comparing these paths. Once the LCA is known, construct the final directions by moving U (up) from the start node to the LCA and then following L or R directions from the LCA to reach the destination node.
This approach works efficiently because each node is visited at most once during traversal. With careful path tracking and string construction, the algorithm achieves O(n) time complexity while using additional space for recursion and path storage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Lowest Common Ancestor and Path Construction | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
The shortest path between any two nodes in a tree must pass through their Lowest Common Ancestor (LCA). The path will travel upwards from node s to the LCA and then downwards from the LCA to node t.
Find the path strings from root → s, and root → t. Can you use these two strings to prepare the final answer?
Remove the longest common prefix of the two path strings to get the path LCA → s, and LCA → t. Each step in the path of LCA → s should be reversed as 'U'.
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').
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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12bool pathToNode(TreeNode* root, int value, vector<char>& path) {
13 if (!root) return false;
14 if (root->val == value) return true;
15 path.push_back('L');
16 if (pathToNode(root->left, value, path)) return true;
17 path.pop_back();
18 path.push_back('R');
19 if (pathToNode(root->right, value, path)) return true;
20 path.pop_back();
21 return false;
22}
23
24string getDirections(TreeNode* root, int startValue, int destValue) {
25 vector<char> startPath, destPath;
26 pathToNode(root, startValue, startPath);
27 pathToNode(root, destValue, destPath);
28 int i = 0;
29 while (i < startPath.size() && i < destPath.size() && startPath[i] == destPath[i]) i++;
30 return string(startPath.size() - i, 'U') + string(destPath.begin() + i, destPath.end());
31}
32
33int main() {
34 TreeNode* root = new TreeNode(5);
35 root->left = new TreeNode(1);
36 root->right = new TreeNode(2);
37 root->left->left = new TreeNode(3);
38 root->right->left = new TreeNode(6);
39 root->right->right = new TreeNode(4);
40
41 cout << getDirections(root, 3, 6) << endl; // Output: "UURL"
42
43 return 0;
44}This C++ implementation follows a similar logic to the Python solution. The pathToNode helper function finds paths to the target nodes using depth-first search, marking directions with 'L' and 'R'. The getDirections function then calculates steps towards the lowest common ancestor and outputs the directions to the destination node.
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'.
Time Complexity: O(n), traversing all nodes for setup. Space Complexity: O(n) due to the parent mapping.
1class TreeNode:
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The LCA helps separate the path into two segments: moving up from the start node and then moving down to the destination node. This avoids unnecessary traversal and simplifies constructing the final direction string.
Yes, similar binary tree path and Lowest Common Ancestor problems frequently appear in FAANG-style interviews. They test understanding of tree traversal, recursion, and path construction logic.
A binary tree combined with recursion or a stack for depth-first search works best. Additionally, strings or lists are used to store the path directions from the root or LCA to the target nodes.
The optimal approach is to find the Lowest Common Ancestor (LCA) of the start and destination nodes. From the start node you move up to the LCA using 'U', and then follow the path from the LCA to the destination using 'L' or 'R'. This can be implemented efficiently using depth-first search.
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.