Skip to content

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

Approach 1: LCA + Build paths

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  string getDirections(TreeNode* root, int startValue, int destValue) {
    string path;
    string pathToStart;
    string pathToDest;
    // only this subtree matters
    dfs(lca(root, startValue, destValue), startValue, destValue, path,
        pathToStart, pathToDest);
    return string(pathToStart.length(), 'U') + pathToDest;
  }

 private:
  TreeNode* lca(TreeNode* root, int p, int q) {
    if (!root || root->val == p || root->val == q)
      return root;
    TreeNode* l = lca(root->left, p, q);
    TreeNode* r = lca(root->right, p, q);
    if (l && r)
      return root;
    return l ? l : r;
  }

  void dfs(TreeNode* root, int p, int q, string& path, string& pathToStart,
           string& pathToDest) {
    if (!root)
      return;
    if (root->val == p)
      pathToStart = path;
    if (root->val == q)
      pathToDest = path;
    path.push_back('L');
    dfs(root->left, p, q, path, pathToStart, pathToDest);
    path.pop_back();
    path.push_back('R');
    dfs(root->right, p, q, path, pathToStart, pathToDest);
    path.pop_back();
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public String getDirections(TreeNode root, int startValue, int destValue) {
    // only this subtree matters
    dfs(lca(root, startValue, destValue), startValue, destValue, new StringBuilder());
    return "U".repeat(pathToStart.length()) + pathToDest;
  }

  private String pathToStart = "";
  private String pathToDest = "";

  private TreeNode lca(TreeNode root, int p, int q) {
    if (root == null || root.val == p || root.val == q)
      return root;
    TreeNode l = lca(root.left, p, q);
    TreeNode r = lca(root.right, p, q);
    if (l != null && r != null)
      return root;
    return l == null ? r : l;
  }

  private void dfs(TreeNode root, int p, int q, StringBuilder path) {
    if (root == null)
      return;
    if (root.val == p)
      pathToStart = path.toString();
    if (root.val == q)
      pathToDest = path.toString();
    dfs(root.left, p, q, path.append('L'));
    path.deleteCharAt(path.length() - 1);
    dfs(root.right, p, q, path.append('R'));
    path.deleteCharAt(path.length() - 1);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
    def lca(root: Optional[TreeNode]) -> Optional[TreeNode]:
      if not root or root.val in (startValue, destValue):
        return root
      l = lca(root.left)
      r = lca(root.right)
      if l and r:
        return root
      return l or r

    def dfs(root: Optional[TreeNode], path: List[chr]) -> None:
      if not root:
        return
      if root.val == startValue:
        self.pathToStart = ''.join(path)
      if root.val == destValue:
        self.pathToDest = ''.join(path)
      path.append('L')
      dfs(root.left, path)
      path.pop()
      path.append('R')
      dfs(root.right, path)
      path.pop()

    dfs(lca(root), [])  # only this subtree matters
    return 'U' * len(self.pathToStart) + ''.join(self.pathToDest)

Approach 2: Build paths and remove common prefix

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  string getDirections(TreeNode* root, int startValue, int destValue) {
    string pathToStart;
    string pathToDest;

    dfs(root, startValue, pathToStart);
    dfs(root, destValue, pathToDest);

    while (!pathToStart.empty() && !pathToDest.empty() &&
           pathToStart.back() == pathToDest.back()) {
      pathToStart.pop_back();
      pathToDest.pop_back();
    }

    return string(pathToStart.length(), 'U') +
           string(rbegin(pathToDest), rend(pathToDest));
  }

 private:
  // build the string in reverse order to avoid creating new copy
  bool dfs(TreeNode* root, int val, string& path) {
    if (root->val == val)
      return true;
    if (root->left && dfs(root->left, val, path))
      path.push_back('L');
    else if (root->right && dfs(root->right, val, path))
      path.push_back('R');
    return !path.empty();
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public String getDirections(TreeNode root, int startValue, int destValue) {
    StringBuilder pathToStart = new StringBuilder();
    StringBuilder pathToDest = new StringBuilder();

    dfs(root, startValue, pathToStart);
    dfs(root, destValue, pathToDest);

    while (pathToStart.length() > 0 && pathToDest.length() > 0 &&
           pathToStart.charAt(pathToStart.length() - 1) ==
               pathToDest.charAt(pathToDest.length() - 1)) {
      pathToStart.setLength(pathToStart.length() - 1);
      pathToDest.setLength(pathToDest.length() - 1);
    }

    return "U".repeat(pathToStart.length()) + pathToDest.reverse().toString();
  }

  // build the string in reverse order to avoid creating new copy
  private boolean dfs(TreeNode root, int val, StringBuilder sb) {
    if (root.val == val)
      return true;
    if (root.left != null && dfs(root.left, val, sb))
      sb.append("L");
    else if (root.right != null && dfs(root.right, val, sb))
      sb.append("R");
    return sb.length() > 0;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
    # buidl the string in reverse order to avoid creating new copy
    def dfs(root: Optional[TreeNode], val: int, path: List[chr]) -> bool:
      if root.val == val:
        return True
      if root.left and dfs(root.left, val, path):
        path.append('L')
      elif root.right and dfs(root.right, val, path):
        path.append('R')
      return len(path) > 0

    pathToStart = []
    pathToDest = []

    dfs(root, startValue, pathToStart)
    dfs(root, destValue, pathToDest)

    while pathToStart and pathToDest and pathToStart[-1] == pathToDest[-1]:
      pathToStart.pop()
      pathToDest.pop()

    return 'U' * len(pathToStart) + ''.join(reversed(pathToDest))
Back to top