LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another 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{"\n"} Output: "UURL"{"\n"} Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.{"\n"}
Example 2:

Input: root = [2,1], startValue = 2, destValue = 1{"\n"} Output: "L"{"\n"} Explanation: The shortest path is: 2 → 1.{"\n"}
Constraints:
-
The number of nodes in the tree is
n
. -
2 <= n <= 105
-
1 <= Node.val <= n
- All the values in the tree are unique.
-
1 <= startValue, destValue <= n
-
startValue != destValue
Problem Link: https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
Solution
Solution
Let denote the path from to .
First consider the case where goes through the root. Let's split this into . We can perform a DFS (depth first search) to get . This path consists of 'L's and 'R's. We can do another DFS to get . Replacing the 'L's and 'R's of with 'U's gives us . Now we can concatenate and to get the answer.
In the general case, may not go through the root. Notice that this path goes up a non-negative number of times (s) before going down a non-negative number of times (s or s). The highest node in this path is known as the LCA (lowest common ancestor) of and .
<img src={require('@site/static/img/2096/1.png').default} style={{ height: 300 }}/> <img src={require('@site/static/img/2096/2.png').default} style={{ height: 300 }}/>
Here, and . Let's remove their longest common prefix, which is . We have and .
<img src={require('@site/static/img/2096/3.png').default} style={{ height: 300 }}/>
Then we replace all characters in with s to obtain . Finally, we get .
Time complexity
Each DFS takes and our string operations never happen on strings exceeding length . The time complexity is .
Space complexity
The strings never exceed length . The space complexity is .
C++ Solution
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10 * right(right) {}
11 * };
12 */
13class Solution {
14public:
15 void getPath(TreeNode *cur, int targetValue, string &path, string &ans) {
16 if (!cur)
17 return;
18 if (cur->val == targetValue)
19 ans = path;
20 path.push_back('L');
21 getPath(cur->left, targetValue, path, ans);
22 path.back() = 'R';
23 getPath(cur->right, targetValue, path, ans);
24 path.pop_back();
25 }
26
27 string getDirections(TreeNode *root, int startValue, int destValue) {
28 string tmpPath, startPath, destPath;
29 getPath(root, startValue, tmpPath, startPath);
30 getPath(root, destValue, tmpPath, destPath);
31 // Find the first point at which the paths diverge
32 auto [itr1, itr2] = mismatch(startPath.begin(), startPath.end(),
33 destPath.begin(), destPath.end());
34 return string(startPath.end() - itr1, 'U') +
35 string(itr2, destPath.end());
36 }
37};
Java Solution
1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode() {}
8 * TreeNode(int val) { this.val = val; }
9 * TreeNode(int val, TreeNode left, TreeNode right) {
10 * this.val = val;
11 * this.left = left;
12 * this.right = right;
13 * }
14 * }
15 */
16class Solution {
17 // We use StringBuilder instead of String because String is immutable,
18 // so appending a character takes O(length of string).
19 // ans is a String[1] instead of String because in Java, arrays are passed by reference.
20 void getPath(TreeNode cur, int targetValue, StringBuilder path, String[] ans) {
21 if (cur == null)
22 return;
23 if (cur.val == targetValue)
24 ans[0] = path.toString();
25 int strLen = path.length();
26 path.append("L");
27 getPath(cur.left, targetValue, path, ans);
28 path.replace(strLen, strLen+1, "R");
29 getPath(cur.right, targetValue, path, ans);
30 path.delete(strLen, strLen+1);
31 }
32 public String getDirections(TreeNode root, int startValue, int destValue) {
33 StringBuilder tmpPath = new StringBuilder();
34 String[] startPath = {""}, destPath = {" "};
35 // Find the first point at which the paths diverge
36 getPath(root, startValue, tmpPath, startPath);
37 getPath(root, destValue, tmpPath, destPath);
38 int i = 0;
39 while (i < Math.min(startPath[0].length(), destPath[0].length()) && startPath[0].charAt(i) == destPath[0].charAt(i))
40 i++;
41 return "U".repeat(startPath[0].length()-i) + destPath[0].substring(i);
42 }
43}
Python Solution
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7class Solution: 8 def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str: 9 # ans is a list so that it passes by reference 10 def getPath(cur, targetValue, path, ans): 11 if cur is None: 12 return 13 if cur.val == targetValue: 14 ans.append(''.join(path)); 15 path.append('L'); 16 getPath(cur.left, targetValue, path, ans) 17 path[-1] = 'R' 18 getPath(cur.right, targetValue, path, ans) 19 path.pop(-1) 20 21 tmpPath = [] 22 startPath = [] 23 destPath = [] 24 getPath(root, startValue, tmpPath, startPath) 25 getPath(root, destValue, tmpPath, destPath) 26 startPath = startPath[0] 27 destPath = destPath[0] 28 29 # Find the first point at which the paths diverge 30 i = 0 31 while i < min(len(startPath), len(destPath)) and startPath[i] == destPath[i]: 32 i += 1 33 return 'U'*(len(startPath)-i) + destPath[i:]