Lowest common ancestor

O(n)

A recursion where each call reports upward whether it found one of the two target nodes below it, so the node where both reports first meet is the split point.

Signals

lowest common ancestor of two nodesdeepest node that is an ancestor of both p and qeach recursive call returns which target(s) it found below itpath from root to each node then compare (alternate approach)binary tree or BST given, find where the two paths split

Template

function lca(node, p, q) {
    if (!node || node === p || node === q) return node;
    const left = lca(node.left, p, q);
    const right = lca(node.right, p, q);
    if (left && right) return node; // p and q split here
    return left || right;
}

Looks similar, isn't

Tree traversal: A plain traversal just visits every node in order and does not carry information back up about what it found. LCA is a specific recursion whose return value reports whether p, q, or both were found in a subtree, so the merge point can be recognized in a single pass.

n nodes, single pass -> O(n) time: each node reports up to its parent whether p, q, or both were found below it, so the split point surfaces after visiting every node once.

Learn this pattern