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

Problem

Step-By-Step Directions From a Binary Tree Node to Another - LeetCodeLeetCode

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

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

    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

O(N) + O(N) + O(N) = 3 O(N) = O(N)

Final is O(N)

Space Complexity

N -> Total Number of node

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)

Final is O(N) for skewed tree

Solution

/**
 * 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;
    }

    
}