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

## Problem

{% embed url="<https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/description/>" %}

## Intuition

* This is a very nice problem as one require multiple concepts. Like
  * **Lowest Common Ancestor**
  * **DFS** : *Tree Traversal and Backtracking* (to get Path b/w nodes)
* First let us make couple of observations and note it down :
  * How to get shortest distance/path b/w two node in Binary Tree?
    * We need to find closest point(from nodes), where path from root to nodes intersect
    * This is nothing but the **LCA**(Lowest Common Ancestor) of two nodes.
  * Now, if we move from **start node to LCA node**, which direction we will follow : `U(up)` , `L(left)` or `R(right)` ?
    * Here we can surely say since LCA always lie above the node, so we will move in upward direction.
    * And there can also be a case when **start node itself is LCA**, so no need to worry in this case.
* Now coming back to our problem, we need to get shortest path from `start -> destination` , or
  * in other words path from

    ```rust
      "start -> LCA" + "LCA -> destination"
      
      -> But we cannot find "start -> LCA" directly. i.e from bottom to up
      -> What we can do instead is first find top to down path 
      		i.e "LCA -> start" , using normal tree traversal algo
      -> and then convert it such that we move in upward direction. (Observation: 2)
      
    ```
* Thus, putting all these together. Lets write a **step-by-step** algorithm to get directions :
  1. First of all find the LCA node of `start` and `destination`.
  2. Then we need to get path from `lca_to_start` and from `lca_to_destination`.
  3. To get path from `root -> node` as a string, we will use `traverse()` function.
     * In this we simply do a simple **DFS** ( kind of pre-order traversal)
     * First explore left path, if node is found. Then return true.
     * Otherwise backtrack and explore right path.
  4. Now that we have both paths, we will convert all chars in `lca_to_start` to `U`, since we will move upward.
  5. At last, concatenate both strings and return combined path.
* Lets see this through an example :

  ```rust
    Given : start = 3, destination = 6
    			
    					  5   ---> LCA(3,6)
    					/   \
    				       1     2
    				      /     /  \
    	        start <---	    '3'   '6'    4
    					   ^
    					   |
    				   destination
    				   
    -> So here node '5' is LCA of start(3) and dest(3)
    -> path from lca_to_start = '5 -> 1 -> 3' = "L L"
    -> path from lca_to_dest = '5 -> 2 -> 6' = "R L"
    
    Also, since we know that shortest path from 
    	# start-> destination = 'start -> LCA' + 'LCA -> destination'
    	
    So, we need to convert (reverse) `lca_to_start` = "U U" , as we move in upward direction
    
    Therefore, final path = "U U" + "R L" = "U U R L"
  ```

## Time Complexity

N -> Total Number of node

O(N) -> LCA

O(N) -> Traverse from LCA to start

O(N) -> Traverse from LCA to dest

{% hint style="info" %}
O(N) + O(N) + O(N) = 3 O(N) = O(N)

Final is `O(N)`
{% endhint %}

## Space Complexity

N -> Total Number of node

O(h) -> LCA stack space&#x20;

O(N) -> In worst case, there is a skewed tree and the path from left most node to right most // node is O(N)&#x20;

{% hint style="info" %}
O(h) + O(N) = O(N)

Final is `O(N)` for skewed tree
{% endhint %}

## Solution

```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 {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        // Time Complexity: 
        // O(N) -> LCA, O(N) -> Traverse from LCA to start, O(N) -> Traverse from LCA to des
        // O(N) + O(N) + O(N) = 3 O(N) = O(N)

        // Space Complexity:
        // O(h) -> LCA stack space
        // O(N) -> In worst case, there is a skewed tree and the path from left most node to right most
        // node is O(N)
        // O(h) + O(N) = O(N)
        TreeNode lca = lcaHelper(root, startValue, destValue);

        List<String> start = new ArrayList<>();
        List<String> end = new ArrayList<>();
        String s = "";

        traverse(lca, start, startValue);
        traverse(lca, end, destValue);

        // Whatever the path is from LCA to startval, we explored it downwards using "L" and "R"
        // But if we have to chart a path from start to LCA, then we only need to move "UP"
        // So we replace the path with equivalent number of steps to UP
        for(String dir: start) s += "U";
        // Append the directions from LCA to destination value
        for(String dir: end) s += dir;

        return s;
    }

    private boolean traverse(TreeNode node, List<String> steps, int destVal) {
        // If node is null, nothing more to traverse, we did not reach the destination
        // So return false
        if(node == null) return false;

        // If we reach a node where its value is equal to destination value,
        // then return true.
        // The constraint of the question is all the nodes have unique values
        if(node.val == destVal) return true;

        // We perform traversal by checking out Left and Right

        
        steps.add("L"); // Add "L" to the step for exploring Left side
        // If we found the destination value by exploring left subtree, return true
        if(traverse(node.left, steps, destVal)) return true;
        // Once the left subtree is completely explored, then we return to the node
        // So we remove the last "L" step
        steps.remove(steps.size() - 1); 

        steps.add("R"); // Add "R" to the step for exploring Right side
        // If we found the destination value by exploring right subtree, return true
        if(traverse(node.right, steps, destVal)) return true;
        // Once the right subtree is completely explored, then we return to the node
        // So we remove the last "R" step
        steps.remove(steps.size() - 1);

        return false;
    }

    private TreeNode lcaHelper(TreeNode root, int start, int dest) {
        // Standard LCA algorithm
        if(root == null) return null;

        if(root.val == start || root.val == dest) return root;

        TreeNode left = lcaHelper(root.left, start, dest);
        TreeNode right = lcaHelper(root.right, start, dest);

        if(left == null) return right;
        else if(right == null) return left;
        else return root;
    }

    
}
```