Lowest Common Ancestor

def lca(root, p, q):
    if not root or root is p or root is q:
        return root           # empty, or an heir
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root           # flares meet here
    return left or right      # pass one up

Lowest Common Ancestor. Given a binary tree and two nodes, p and q, find their lowest common ancestor: the deepest node with both of them below it.

Take this tree. For five and one, the answer is the root, three. For five and four, it's five itself: a node counts as its own ancestor.

The simple way records the path from the root to each node, then compares the paths until they split. Two searches, plus extra memory for the paths.

Here's the trick: one pass, from the bottom up. Each node asks both children what they found. An empty spot finds nothing; p or q reports itself. If both sides found something, the heirs meet here: this node is the answer. Otherwise, pass up whichever side found one.

In code: if the node is empty, p or q, return it. Search left and right. If both came back, return this node; otherwise, the one that did.

Let's find heirs six and four. Six is an heir: it sends up a flare. Under two, seven finds nothing and four is an heir, so two passes four's flare up. Now five has flares from both sides: five is the ancestor. Three's right side finds nothing, so three passes five up. The answer is five.

Each node is visited once, so the time is O of n. The recursion goes as deep as the tree, so the space is O of h, its height.

Two heirs send up flares, and the first banner to catch both is the ancestor. That's Lowest Common Ancestor.