# Step-By-Step Directions From a Binary Tree Node to Another
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another)
Canonical: https://scaleengineer.com/dsa/problems/step-by-step-directions-from-a-binary-tree-node-to-another
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** String, Tree, Binary Tree
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Databricks](https://scaleengineer.com/companies/databricks)
---
## Problem
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:**

![](https://assets.glich.co/dsa/step-by-step-directions-from-a-binary-tree-node-to-another/image0.png) 

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

![](https://assets.glich.co/dsa/step-by-step-directions-from-a-binary-tree-node-to-another/image1.png) 

**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`

# Approaches
## Graph Conversion and BFS
This approach transforms the binary tree into a general graph and then applies a standard shortest path algorithm, Breadth-First Search (BFS). Since we need to travel upwards ('U'), the graph must include edges from children to parents. This is achieved by first building a map to store parent pointers for each node.
**Time:** O(N), where N is the number of nodes. The initial traversal to build the parent map takes O(N). The subsequent BFS also visits each node and edge at most once, which also takes O(N) time. · **Space:** O(N), where N is the number of nodes in the tree. The `parentMap` can store up to N-1 entries. In the worst-case scenario, the BFS `queue` and `visited` set can also store up to O(N) nodes.
**Pros:** It is a general and robust approach for finding the shortest path in any graph, not just trees.; The correctness is guaranteed by the properties of Breadth-First Search for unweighted graphs.
**Cons:** Requires significant extra space (O(N)) to store the parent map, the BFS queue, and the visited set.; The implementation is more involved compared to solutions that work directly on the tree structure.; Has higher constant factors for time and space compared to more optimized tree-specific approaches.
### Explanation
1.  **Build Parent Map:** First, we traverse the entire tree to build a data structure, typically a `HashMap`, that maps each node to its parent. This allows us to navigate upwards from any node. While building this map, we can also locate the reference to the `startNode`.
2.  **Perform BFS:** With the parent pointers available, the tree can be treated as a graph. We initiate a BFS starting from the `startNode`. The queue used for BFS will store not just the nodes to visit, but also the path string of directions taken to reach that node from the `startNode`.
3.  **Exploration and Path Finding:** In each iteration of the BFS, we dequeue a node and its path. If this node is the destination, we have found the shortest path and can return the associated path string. Otherwise, we explore its neighbors: the parent (using our map), the left child, and the right child. For each unvisited neighbor, we form the new path by appending the correct direction ('U', 'L', or 'R') and add it to the queue and a `visited` set.

```java
// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

// A simple Pair class to use in the queue
class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public K getKey() { return key; }
    public V getValue() { return value; }
}

class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        TreeNode startNode = findStartNodeAndBuildParentMap(root, startValue, parentMap);

        Queue<Pair<TreeNode, String>> queue = new LinkedList<>();
        queue.offer(new Pair<>(startNode, ""));
        Set<TreeNode> visited = new HashSet<>();
        visited.add(startNode);

        while (!queue.isEmpty()) {
            Pair<TreeNode, String> current = queue.poll();
            TreeNode currentNode = current.getKey();
            String currentPath = current.getValue();

            if (currentNode.val == destValue) {
                return currentPath;
            }

            // Move Up (to parent)
            TreeNode parent = parentMap.get(currentNode);
            if (parent != null && !visited.contains(parent)) {
                visited.add(parent);
                queue.offer(new Pair<>(parent, currentPath + "U"));
            }

            // Move Left
            if (currentNode.left != null && !visited.contains(currentNode.left)) {
                visited.add(currentNode.left);
                queue.offer(new Pair<>(currentNode.left, currentPath + "L"));
            }

            // Move Right
            if (currentNode.right != null && !visited.contains(currentNode.right)) {
                visited.add(currentNode.right);
                queue.offer(new Pair<>(currentNode.right, currentPath + "R"));
            }
        }
        return ""; // Should not be reached given the problem constraints
    }

    private TreeNode findStartNodeAndBuildParentMap(TreeNode node, int startValue, Map<TreeNode, TreeNode> parentMap) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        TreeNode startNode = null;

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (current.val == startValue) {
                startNode = current;
            }
            if (current.left != null) {
                parentMap.put(current.left, current);
                queue.offer(current.left);
            }
            if (current.right != null) {
                parentMap.put(current.right, current);
                queue.offer(current.right);
            }
        }
        return startNode;
    }
}
```
### Algorithm
- **Build Parent Map:** Traverse the tree using a level-order traversal (BFS) to populate a `Map<TreeNode, TreeNode>` that stores the parent of each node. During this traversal, also find the `TreeNode` object corresponding to the `startValue`.
- **Perform BFS for Shortest Path:** Start a Breadth-First Search (BFS) from the `startNode`.
- **Queue State:** The BFS queue will store pairs of `(TreeNode, path_string)`, representing the current node and the path taken to reach it.
- **Track Visited Nodes:** Use a `Set<TreeNode>` to keep track of visited nodes to prevent cycles (e.g., moving from a child to parent and back) and avoid redundant computations.
- **Explore Neighbors:** In each step of the BFS, for the current node, explore its three potential neighbors: its parent (from the map), its left child, and its right child.
- **Path Construction:** For each valid, unvisited neighbor, append the corresponding direction ('U', 'L', or 'R') to the current path string and enqueue the neighbor along with the new path.
- **Termination:** BFS naturally finds the shortest path in an unweighted graph. Therefore, the first time the `destNode` is reached, the path associated with it is the shortest. Return this path immediately.

## Two Separate Path-Finding Traversals
This approach avoids building an explicit graph. Instead, it finds the path from the root to the start node and the path from the root to the destination node using two separate traversals. The shortest path between the two nodes must pass through their Lowest Common Ancestor (LCA). By comparing the two root-to-node paths, we can identify the LCA, trim the common path segment, and then construct the final directions.
**Time:** O(N), where N is the number of nodes. In the worst case, each of the two `findPath` calls might traverse the entire tree. Thus, the total time is O(N) + O(N) = O(N). · **Space:** O(H), where H is the height of the tree. This space is consumed by the recursion stack for DFS and the `StringBuilder`s used to store the paths. In the worst case of a skewed tree, H can be equal to N, making the space complexity O(N).
**Pros:** Simpler to implement than the graph conversion approach as it works directly with the tree structure.; Does not require building large auxiliary data structures like a parent map for the entire tree.
**Cons:** This approach is inefficient because it traverses the tree twice. Many nodes might be visited in both the first and second traversals, leading to redundant computations.
### Explanation
The core idea is that the path from any node `A` to node `B` can be seen as moving from `A` up to their Lowest Common Ancestor (LCA), and then down to `B`. We can find the paths from the root to both the start and destination nodes. The common part of these paths leads to the LCA.

1.  **Find Paths from Root:** We perform two separate Depth-First Searches (DFS) from the root. The first DFS finds the path to `startValue`, and the second finds the path to `destValue`. Each DFS records the sequence of 'L' (left) and 'R' (right) moves in a string.
2.  **Process Paths:** After obtaining the two path strings, we find their common prefix. For example, if `pathToStart` is "RLR" and `pathToDest` is "RLL", the common prefix is "RL". This means the LCA is reached by taking the path "RL" from the root.
3.  **Generate Directions:** The path from the start node to the LCA is the reverse of the unique part of `pathToStart`, which translates to a series of 'U' (up) moves. The path from the LCA to the destination is simply the unique part of `pathToDest`. The final direction string is the concatenation of these two parts.

```java
class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder pathToStart = new StringBuilder();
        StringBuilder pathToDest = new StringBuilder();

        // First traversal to find path to startValue
        findPath(root, startValue, pathToStart);
        // Second traversal to find path to destValue
        findPath(root, destValue, pathToDest);

        int i = 0;
        // Find the length of the common prefix (path to LCA)
        while (i < pathToStart.length() && i < pathToDest.length() &&
               pathToStart.charAt(i) == pathToDest.charAt(i)) {
            i++;
        }

        StringBuilder result = new StringBuilder();
        // Add 'U' for each step from start to LCA
        for (int j = 0; j < pathToStart.length() - i; j++) {
            result.append('U');
        }

        // Add steps from LCA to destination
        result.append(pathToDest.substring(i));

        return result.toString();
    }

    private boolean findPath(TreeNode node, int target, StringBuilder path) {
        if (node == null) {
            return false;
        }
        if (node.val == target) {
            return true;
        }

        path.append('L');
        if (findPath(node.left, target, path)) {
            return true;
        }
        path.deleteCharAt(path.length() - 1); // Backtrack

        path.append('R');
        if (findPath(node.right, target, path)) {
            return true;
        }
        path.deleteCharAt(path.length() - 1); // Backtrack

        return false;
    }
}
```
### Algorithm
- **Find Path to Start:** Implement a recursive DFS helper function, `findPath(node, target, path)`, that traverses the tree to find the `target` value. The function builds the path (a sequence of 'L' and 'R') in a `StringBuilder` and returns `true` once the target is found.
- **Find Path to Destination:** Call the `findPath` function once to get the path from the root to the `startValue` (`pathToStart`).
- **Second Traversal:** Call the `findPath` function a second time to get the path from the root to the `destValue` (`pathToDest`).
- **Find Common Prefix (LCA):** Iterate through both `pathToStart` and `pathToDest` to find the length of their longest common prefix. The node at the end of this common path is the Lowest Common Ancestor (LCA).
- **Construct Final Path:**
  - The path from the start node up to the LCA consists of 'U' moves. The number of 'U's is `pathToStart.length() - commonPrefixLength`.
  - The path from the LCA down to the destination node is the non-common part of `pathToDest`, which is `pathToDest.substring(commonPrefixLength)`.
  - Concatenate these two parts to form the final result.

## Optimized Single Traversal to Find Paths
This is the most efficient approach. It improves upon the two-traversal method by finding the paths from the root to both the start and destination nodes in a single DFS traversal, thus avoiding redundant work. After finding both paths, it identifies the common prefix (representing the path to the LCA) and constructs the final directions.
**Time:** O(N). The tree is traversed only once. The subsequent path comparison and string building operations take O(H) time, where H is the tree height (at most N). The overall time complexity is dominated by the single traversal. · **Space:** O(H), where H is the height of the tree. This space is for the recursion stack and the path `StringBuilder`s. In the worst case of a skewed tree, H can be N, leading to O(N) space complexity.
**Pros:** Most time-efficient approach as it traverses the tree only once, minimizing redundant node visits.; Avoids the overhead of creating explicit graph structures like parent maps.; Cleanly separates the path-finding logic from the direction-generation logic.
**Cons:** The recursive function signature can be slightly more complex due to the need to pass around multiple path builders or use class members to store the results.; While asymptotically optimal, it still requires O(N) space for the recursion stack and path strings in the worst case of a skewed tree.
### Explanation
This approach refines the previous one by merging the two separate DFS traversals into one. A single pass over the tree is sufficient to find the paths to both the start and destination nodes.

1.  **Single Traversal:** We design a DFS function that searches for both `startValue` and `destValue` simultaneously. This function keeps track of the path from the root to the current node. When either target node is found, its corresponding path from the root is recorded. We can use class member variables to store the two paths once they are found.
2.  **Path Processing:** Once the traversal is complete (or as soon as both paths are found), the procedure is the same as in the two-traversal approach. We find the longest common prefix of the two paths. This prefix corresponds to the path from the root to the LCA.
3.  **Direction Generation:** The directions are then constructed by first generating 'U's for every step in the non-common part of the start path, and then appending the non-common part of the destination path.

```java
class Solution {
    private StringBuilder pathToStart = null, pathToDest = null;

    public String getDirections(TreeNode root, int startValue, int destValue) {
        // Find both paths in a single traversal
        findPaths(root, startValue, destValue, new StringBuilder());

        int i = 0;
        // Find the length of the common prefix
        while (i < pathToStart.length() && i < pathToDest.length() &&
               pathToStart.charAt(i) == pathToDest.charAt(i)) {
            i++;
        }

        StringBuilder result = new StringBuilder();
        // Append 'U' for the path from start to LCA
        for (int j = 0; j < pathToStart.length() - i; j++) {
            result.append('U');
        }

        // Append the path from LCA to destination
        result.append(pathToDest.substring(i));
        return result.toString();
    }

    private void findPaths(TreeNode node, int startVal, int destVal, StringBuilder currentPath) {
        // Base case or if both paths are already found
        if (node == null || (pathToStart != null && pathToDest != null)) {
            return;
        }

        if (node.val == startVal) {
            pathToStart = new StringBuilder(currentPath);
        }
        if (node.val == destVal) {
            pathToDest = new StringBuilder(currentPath);
        }

        // Explore left subtree
        currentPath.append('L');
        findPaths(node.left, startVal, destVal, currentPath);
        currentPath.deleteCharAt(currentPath.length() - 1); // Backtrack

        // Optimization: if both found, no need to check right subtree
        if (pathToStart == null || pathToDest == null) { 
            // Explore right subtree
            currentPath.append('R');
            findPaths(node.right, startVal, destVal, currentPath);
            currentPath.deleteCharAt(currentPath.length() - 1); // Backtrack
        }
    }
}
```
### Algorithm
- **Single DFS Traversal:** Create a single recursive DFS function, `findPaths(node, startVal, destVal, currentPath, ...)`.
- **Path Discovery:** This function traverses the tree from the root. It maintains a `currentPath` from the root to the current node. When it encounters `startVal`, it saves a copy of `currentPath` as `pathToStart`. Similarly, when it finds `destVal`, it saves the path as `pathToDest`.
- **Optimization:** The traversal can be pruned. Once both `pathToStart` and `pathToDest` have been found, the recursion can stop exploring further branches.
- **Process Paths:** After the single traversal completes, we will have both path strings. The rest of the logic is identical to the previous approach:
  - Find the length of the common prefix `i`.
  - Generate `pathToStart.length() - i` 'U' moves.
  - Append `pathToDest.substring(i)`.
  - Return the combined string.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < Integer , List < List < String >>> edges ; private Set < Integer > visited ; private String ans ; public String getDirections ( TreeNode root , int startValue , int destValue ) { edges = new HashMap <>(); visited = new HashSet <>(); ans = null ; traverse ( root ); dfs ( startValue , destValue , new ArrayList <>()); return ans ; } private void traverse ( TreeNode root ) { if ( root == null ) { return ; } if ( root . left != null ) { edges . computeIfAbsent ( root . val , k -> new ArrayList <>()) . add ( Arrays . asList ( String . valueOf ( root . left . val ), "L" )); edges . computeIfAbsent ( root . left . val , k -> new ArrayList <>()) . add ( Arrays . asList ( String . valueOf ( root . val ), "U" )); } if ( root . right != null ) { edges . computeIfAbsent ( root . val , k -> new ArrayList <>()) . add ( Arrays . asList ( String . valueOf ( root . right . val ), "R" )); edges . computeIfAbsent ( root . right . val , k -> new ArrayList <>()) . add ( Arrays . asList ( String . valueOf ( root . val ), "U" )); } traverse ( root . left ); traverse ( root . right ); } private void dfs ( int start , int dest , List < String > t ) { if ( visited . contains ( start )) { return ; } if ( start == dest ) { if ( ans == null || ans . length () > t . size ()) { ans = String . join ( "" , t ); } return ; } visited . add ( start ); if ( edges . containsKey ( start )) { for ( List < String > item : edges . get ( start )) { t . add ( item . get ( 1 )); dfs ( Integer . parseInt ( item . get ( 0 )), dest , t ); t . remove ( t . size () - 1 ); } } } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} startValue * @param {number} destValue * @return {string} */ var getDirections =
  function (root, startValue, destValue) {
    const lca = (node, p, q) => {
      if (node === null || [p, q].includes(node.val)) {
        return node;
      }
      const left = lca(node.left, p, q);
      const right = lca(node.right, p, q);
      return left && right ? node : (left ?? right);
    };
    const dfs = (node, x, path) => {
      if (node === null) {
        return false;
      }
      if (node.val === x) {
        return true;
      }
      path.push(" L ");
      if (dfs(node.left, x, path)) {
        return true;
      }
      path[path.length - 1] = " R ";
      if (dfs(node.right, x, path)) {
        return true;
      }
      path.pop();
      return false;
    };
    const node = lca(root, startValue, destValue);
    const pathToStart = [];
    const pathToDest = [];
    dfs(node, startValue, pathToStart);
    dfs(node, destValue, pathToDest);
    return " U ".repeat(pathToStart.length) + pathToDest.join("");
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: unordered_map < int , vector < pair < int , char >>> edges ; unordered_set < int > visited ; string ans ; string getDirections ( TreeNode * root , int startValue , int destValue ) { ans = "" ; traverse ( root ); string t = "" ; dfs ( startValue , destValue , t ); return ans ; } void traverse ( TreeNode * root ) { if ( ! root ) return ; if ( root -> left ) { edges [ root -> val ]. push_back ({ root -> left -> val , 'L' }); edges [ root -> left -> val ]. push_back ({ root -> val , 'U' }); } if ( root -> right ) { edges [ root -> val ]. push_back ({ root -> right -> val , 'R' }); edges [ root -> right -> val ]. push_back ({ root -> val , 'U' }); } traverse ( root -> left ); traverse ( root -> right ); } void dfs ( int start , int dest , string & t ) { if ( visited . count ( start )) return ; if ( start == dest ) { if ( ans == "" || ans . size () > t . size ()) ans = t ; return ; } visited . insert ( start ); if ( edges . count ( start )) { for ( auto & item : edges [ start ]) { t += item . second ; dfs ( item . first , dest , t ); t . pop_back (); } } } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def getDirections ( self , root : Optional [ TreeNode ], startValue : int , destValue : int ) -> str : edges = defaultdict ( list ) ans = None visited = set () def traverse ( root ): if not root : return if root . left : edges [ root . val ]. append ([ root . left . val , 'L' ]) edges [ root . left . val ]. append ([ root . val , 'U' ]) if root . right : edges [ root . val ]. append ([ root . right . val , 'R' ]) edges [ root . right . val ]. append ([ root . val , 'U' ]) traverse ( root . left ) traverse ( root . right ) def dfs ( start , dest , t ): nonlocal ans if start in visited : return if start == dest : if ans is None or len ( ans ) > len ( t ): ans = '' . join ( t ) return visited . add ( start ) for d , k in edges [ start ]: t . append ( k ) dfs ( d , dest , t ) t . pop () traverse ( root ) dfs ( startValue , destValue , []) return ans
```