Lowest common ancestor

Two nodes in a tree always share some ancestors: at least the root. The lowest one they share tells you where their paths from the root split. Finding it is a classic tree question, and the method depends on what the tree gives you.

What it is

The lowest common ancestor (LCA) of two nodes p and q is the deepest node that has both of them in its subtree. A node counts as being in its own subtree, so if p is above q, the answer is p itself.

Some places it is used:

• The number of edges between two nodes is depth(p) + depth(q) − 2 · depth(lca): up from p to the LCA, then down to q.
• The closest folder that contains two files is the LCA of the two files in the folder tree.
• Version control: git merge-base finds the last commit two branches share. Commits form a graph rather than a tree, but the idea is the same.

In a search tree

In a BST, the keys say which way to go. Start at the root. If both keys are smaller than the node’s key, both nodes are in the left subtree: go left. If both are bigger, go right. Otherwise they are on different sides (or one of them is this node), so the paths split here, and this node is the answer. Step through the first variant:

def lca_bst(root, p, q):
    node = root
    while True:
        if p < node.value and q < node.value:
            node = node.left
        elif p > node.value and q > node.value:
            node = node.right
        else:
            return node

One path from the root: O(h) time and O(1) extra space.

In any binary tree

Without sorted keys, there is no way to steer, so you must search. The method is to search for both values at once, with one recursive function. find(node) reports what it found in the subtree of node:

• None, if neither value is in the subtree;
• the node holding p or q, if it meets one;
• the answer, once both values have been found on different sides of a node.

def lca(root, p, q):
    def find(node):
        if node is None or node.value == p or node.value == q:
            return node
        a = find(node.left)
        b = find(node.right)
        if a is not None and b is not None:
            return node             # one value on each side
        return a if a is not None else b
    return find(root)

Step through the second variant of the figure to see the answers passed up from the bottom. Why is the result right?

• If p and q are in different subtrees of some node, the two calls below it each return something, and that node returns itself. It is the lowest such node, because calls finish from the bottom up and pass the answer on unchanged.
• If q is below p, the call at p returns p at once, without looking further. No other branch finds anything, so p is passed up to the root. That is correct: p is the answer.

This version assumes both values are in the tree, as practice TREE-P5 promises. If one might be missing, the function would wrongly return the other one; a full solution counts how many of the two it actually found.

With parent links

Some trees store a parent reference in every node. Then you can climb from p and q towards the root. Two simple ways:

• Collect all of p’s ancestors in a set. Then climb from q until you reach a node in the set. O(h) time and space.
• Find both depths. Move the deeper node up until both are at the same depth, then move both up together until they meet. O(h) time and O(1) space. The same idea finds where two linked lists join.

If a tree has no parent links, one traversal can record them in a dict, as the second hint of TREE-P5 suggests: the dict maps each value to its parent’s value.