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

Approach 1: LCA + Build paths

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

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 == nullptr || root->val == p || root->val == q)
      return root;
    TreeNode* left = lca(root->left, p, q);
    TreeNode* right = lca(root->right, p, q);
    if (left != nullptr && right != nullptr)
      return root;
    return left == nullptr ? right : left;
  }

  void dfs(TreeNode* root, int p, int q, string& path, string& pathToStart,
           string& pathToDest) {
    if (root == nullptr)
      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();
  }
};

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 left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left != null && right != null)
      return root;
    return left == null ? right : left;
  }

  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);
  }
}

class Solution:
  def getDirections(
      self,
      root: TreeNode | None,
      startValue: int,
      destValue: int,
  ) -> str:
    def lca(root: TreeNode | None) -> TreeNode | None:
      if not root or root.val in (startValue, destValue):
        return root
      left = lca(root.left)
      right = lca(root.right)
      if left and right:
        return root
      return left or right

    def dfs(root: TreeNode | None, path: list[str]) -> 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)$

C++JavaPython

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{pathToDest.rbegin(), pathToDest.rend()};
  }

 private:
  // Builds the string in reverse order to avoid creating a 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();
  }
};

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();
  }

  // Builds the string in reverse order to avoid creating a 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;
  }
}

class Solution:
  def getDirections(
      self,
      root: TreeNode | None,
      startValue: int,
      destValue: int,
  ) -> str:
    def dfs(root: TreeNode | None, val: int, path: list[str]) -> bool:
      """Builds the string in reverse order to avoid creating a new copy."""
      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))