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

In this guide, you will get 2096. Step-By-Step Directions From a Binary Tree Node to Another LeetCode Solution with the best time and space complexity. The solution to Step-By-Step Directions From a Binary Tree Node to Another problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Step-By-Step Directions From a Binary Tree Node to Another solution in C++
4. Step-By-Step Directions From a Binary Tree Node to Another solution in Java
5. Step-By-Step Directions From a Binary Tree Node to Another solution in Python
6. Additional Resources

Problem Statement of Step-By-Step Directions From a Binary Tree Node to Another

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:

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

Complexity Analysis

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

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

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();
  }
};
/* code provided by PROGIEZ */

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

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);
  }
}
// code provided by PROGIEZ

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

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)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.