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

#binary-trees

Problem

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

Intuition

Explained in the code

Time Complexity

O(N) -> LCA
O(N) -> Traverse from LCA to start
O(N) -> Traverse from LCA to dest

Total time complexity = 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)

Total Space complexity = O(h) + O(N) = O(N)

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