Lowest common ancestor

How does Lowest common ancestor work?

Ask every node the same question. Does either target sit inside my subtree?

An empty node answers no. A node that is itself a target answers with itself.

Otherwise ask both children. Each one returns a node or nothing.

If both children answer with something, this node is the ancestor. The two targets split right here.

If only one answers, pass that answer straight up. The split has not happened yet.

The first node where both sides answer is the deepest one. Nothing above it can be lower.

1. at node 6: foundLooking for 6 and 2. Node 6 answers with itself.
2. at node 2: foundNode 2 also answers with itself.
3. at node 5: both sides answeredThe two targets split here. Node 5 is the answer.
4. at node 3: only the left answeredThe right subtree found nothing. Node 5 is passed up.
5. answer = 5One pass over the tree. No node was visited twice.

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

A worked example of Lowest common ancestor

Ancestor inside a search tree

Both nodes live in a binary search tree. Find their lowest common ancestor.

A node counts as an ancestor of itself here.

The values themselves say which direction to walk.

If both targets are smaller, go left; if both are larger, go right. The first node between them is the answer.

function lowestCommonAncestor(root, p, q) {
    let node = root;

    while (node) {
        if (p.val < node.val && q.val < node.val) {
            node = node.left;
        } else if (p.val > node.val && q.val > node.val) {
            node = node.right;
        } else {
            return node; // the values split here, or one of them is this node
        }
    }

    return null;
}

When should you use Lowest common ancestor?

These phrases in a problem statement point here:

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

What is Lowest common ancestor confused with?

• Binary search tree: In a search tree the values alone point the way. In a plain tree both subtrees must be asked.
• Tree traversal: That page is about the three visit orders. This uses post-order to answer one question.
• Union-find (disjoint set): Tarjan's offline algorithm answers many pairs with a disjoint set. A single pair does not need it.
• DP on trees: DP on trees carries computed values upward. Here the thing carried up is only found or not found.

Common mistakes with Lowest common ancestor

• Searching for each node separately

  Two searches plus a path comparison is far more work. One post-order pass answers it directly.

• Forgetting a node can be its own ancestor

  If one target sits above the other, it is the answer. Return the node as soon as it matches.

• Assuming both nodes are present

  If one is missing, the pass returns the other one. Check presence when absence is allowed.

• Using the search-tree shortcut on a plain tree

  Comparing values only works when the order is guaranteed. Otherwise both subtrees must be asked.

Which interview problems use Lowest common ancestor?

• Lowest common ancestor of a binary tree: The plain form: one post-order pass.
• Lowest common ancestor of a BST: The values alone decide the direction.
• LCA with parent pointers: Walk upward from both nodes and meet.
• LCA of the deepest leaves: Carry the depth up alongside the node.
• Distance between two nodes: Both depths minus twice the ancestor's depth.
• Smallest subtree with all the deepest nodes: The same shape with different targets.
• Step-by-step directions between nodes: Find the ancestor, then build both paths.

What is the time and space complexity of Lowest common ancestor?

O(n)

n nodes give O(n) for one query. Many queries want binary lifting, at O(log n) each.