AlgoDaily - Lowest Common Ancestor

We'd like to find the LCA of 1 and 8. So start from 7, and compare 7 to 1 (greater) and 8 (less). It's in between, so we know it's the LCA!

What if we were looking to find the LCA of 1 and 5 instead?. Starting from 7, if we compare 7 to 1, it's greater. But 7 is ALSO greater than 5 -- it's greater than both.

That indicates that, from 7, we want to traverse left since we're currently to the right of both nodes.

xxxxxxxxxx
 
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
​
function leastCommonAncestor(root, node1, node2) {
    if (root.val > node1 && root.val > node2) {
        return leastCommonAncestor(root.left, node1, node2);
    } else if (root.val < node1 && root.val < node2) {
        return leastCommonAncestor(root.right, node1, node2);
    } else {
        return root;
    }
}
​
const root = new TreeNode(6);
root.left = new TreeNode(2);
root.right = new TreeNode(8);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(9);
console.log(leastCommonAncestor(root, 2, 8).val);

Programming Categories

Popular Lessons