LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another Solution

Solution

Let $\text{path(node1, node2)}$ denote the path from $\text{node1}$ to $\text{node2}$.

First consider the case where $\text{path(start, end)}$ goes through the root. Let's split this into $\text{path(start, root)} + \text{path(root, end)}$. We can perform a DFS (depth first search) to get $\text{path(root, end)}$. This path consists of 'L's and 'R's. We can do another DFS to get $\text{path(root, start)}$. Replacing the 'L's and 'R's of $\text{path(root, start)}$ with 'U's gives us $\text{path(start, root)}$. Now we can concatenate $\text{path(start, root)}$ and $\text{path(root, end)}$ to get the answer.

In the general case, $\text{path(start, end)}$ may not go through the root. Notice that this path goes up a non-negative number of times ($\verb|"U"|$s) before going down a non-negative number of times ($\verb|"L"|$s or $\verb|"R"|$s). The highest node in this path is known as the LCA (lowest common ancestor) of $\text{start}$ and $\text{end}$.

<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, $\text{path(root, start)} = \verb|"RRLLR"|$ and $\text{path(root, end)} = \verb|"RRRL"|$. Let's remove their longest common prefix, which is $\verb|"RR"|$. We have $\text{path(LCA, start)} = \verb|"LLR"|$ and $\text{path(LCA, end)} = \verb|"RL"|$.

<img src={require('@site/static/img/2096/3.png').default} style={{ height: 300 }}/>

Then we replace all characters in $\text{path(root, start)}$ with $\verb|"U"|$s to obtain $\text{path(start, lca)} = \verb|"UUU"|$. Finally, we get $\text{path(start, end)} = \text{path(start, LCA)} + \text{path(LCA, end)} = \verb|"UUU"| + \verb|"RL"| = \verb|"UUURL"|$.

Time complexity

Each DFS takes $\mathcal{O}(n)$ and our string operations never happen on strings exceeding length $\mathcal{O}(n)$. The time complexity is $\mathcal{O}(n)$.

Space complexity

The strings never exceed length $\mathcal{O}(n)$. The space complexity is $\mathcal{O}(n)$.

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:]