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

solution.js

/*
https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/

IDEA:
- If we find the lowest common ancestor of the two nodes we're looking for, then we just
  need to find the path from the start to the LCA, and from the LCA to the target.
- Maintain two stacks; one for the start, and one for the end.
  - The path from the LCA to the start node will just be some number of 'U's, because
     the LCA must be equal to or above the start node (by definition). 
  - The path from the LCA to the end node will be some number of 'L's or 'R's. 
  - Push and pop at the right moments to maintain the 'search stack', then freeze each
    stack as soon as we find the thing that stack is looking for. 
*/
var getDirections = function(root, startValue, destValue) {
    const lca = lowestCommonAncestor(root, startValue, destValue);
    
    const sStack = [];
    const dStack = [];
    
    const dfs = (node) => {
        if(!node || (sStack.locked && dStack.locked)) return;
        if(node.val === startValue) sStack.locked = true;
        if(node.val === destValue) dStack.locked = true;
        
        if(!sStack.locked) sStack.push('U');
        if(!dStack.locked) dStack.push('L');
        dfs(node.left);
        
        if(!dStack.locked) dStack.pop();
        if(!dStack.locked) dStack.push('R');
        dfs(node.right);
        if(!dStack.locked) dStack.pop();
        if(!sStack.locked) sStack.pop();
    };
    
    dfs(lca);
    
    return sStack.join('') + dStack.join('');
};

const lowestCommonAncestor = function(root, p, q) {
    const dfs = (node) => {
        if(!node) return [null, false, false];
        
        const [leftResult, leftHasP, leftHasQ] = dfs(node.left);
        const [righResult, righHasP, righHasQ] = dfs(node.right);

        if(leftResult || righResult) return [leftResult || righResult, true, true];
        
        if((leftHasP || leftHasQ) && (righHasP || righHasQ)) return [node, true, true];
        
        const hasP = leftHasP || righHasP || node.val === p;
        const hasQ = leftHasQ || righHasQ || node.val === q;
        
        if(hasP && hasQ) return [node, true, true];
        return [null, hasP, hasQ];
    };
    
    return dfs(root)[0];
};

// 🤦‍♂️. After thinking about it, this cleans up much better to the following:
var getDirections = function(root, startValue, destValue) {   
    const dfs = (node, target, stack) => {
        if(!node) return false;
        if(node.val === target) return true;
        
        if(dfs(node.left, target, stack)){
            stack.push('L');
            return true;
        }
        
        if(dfs(node.right, target, stack)){
            stack.push('R');
            return true;
        }
        
        return false;
    };
    
    const sStack = [];
    const dStack = [];
    dfs(root, startValue, sStack);
    dfs(root, destValue, dStack);
    
    // remove redundances in the two stacks
    while(sStack.length && dStack.length && sStack.at(-1) === dStack.at(-1)){
        sStack.pop();
        dStack.pop();
    }
    
    return sStack.map(() => 'U').join('') + dStack.reverse().join('');
};