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.

Sources: Wikipedia: Lowest common ancestor

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

interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

function lca(node: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    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;
}

def lca(node, p, q):
    if not node or node is p or node is q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right:
        return node  # p and q split here
    return left or right

function lca(?TreeNode $node, TreeNode $p, TreeNode $q): ?TreeNode {
    if ($node === null || $node === $p || $node === $q) return $node;
    $left = lca($node->left, $p, $q);
    $right = lca($node->right, $p, $q);
    if ($left !== null && $right !== null) return $node; // split point
    return $left ?? $right;
}

    public static TreeNode lca(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null || node == p || node == q) return node;
        TreeNode left = lca(node.left, p, q);
        TreeNode right = lca(node.right, p, q);
        if (left != null && right != null) return node; // p and q split here
        return left != null ? left : right;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static TreeNode Lca(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null || node == p || node == q) return node;
        TreeNode left = Lca(node.left, p, q);
        TreeNode right = Lca(node.right, p, q);
        if (left != null && right != null) return node; // p and q split here
        return left ?? right;
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode 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?

Use Lowest common ancestor when the problem statement says “lowest common ancestor of two nodes”, “deepest node that is an ancestor of both p and q” or “each recursive call returns which target(s) it found below it”. A solution built on it usually runs in O(n).

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Lowest common ancestor confused with?

Lowest common ancestor is most often confused with Binary search tree, Tree traversal, Union-find (disjoint set) and DP on trees.

• 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?

Interview problems solved with Lowest common ancestor include Lowest common ancestor of a binary tree, Lowest common ancestor of a BST, LCA with parent pointers, LCA of the deepest leaves, Distance between two nodes, Smallest subtree with all the deepest nodes and Step-by-step directions between nodes.

• 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?

The target complexity of Lowest common ancestor is O(n).

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