Lowest Common Ancestor (Binary Lifting)

The lowest common ancestor (LCA) of two nodes in a rooted tree is the deepest node that is an ancestor of both. A naive walk-up is O(n) per query. Binary lifting precomputes, for every node, its ancestors at distances 1, 2, 4, 8, … — a table of sparse ancestors — so each query answers in O(log n) by jumping in powers of two.

In the example tree (built by inserting 12, 10, 14, 15, 5, 4, 2), LCA(2, 15) = 12: node 2 lives at depth 4, node 15 at depth 2, and node 12 is the deepest node that sits above both of them.

Intuition

Any number can be written as a sum of distinct powers of two — that is just its binary representation. So any vertical distance up the tree can be covered by a handful of power-of-two jumps. If a node must climb 13 levels, that is 8 + 4 + 1: three hops instead of thirteen.

LCA needs two phases. First we make the two nodes level, because the answer is an ancestor of both and you can only compare nodes that are the same height. Then we raise both nodes together as high as we can without letting them collide. The rule "only jump if it keeps them different" lands us on the two distinct children directly beneath the LCA — and one final parent step reveals it.

Walk through it

Step through the animation. After the swap, u rides the deeper node 2 (depth 4) and v rides node 15 (depth 2).

Equalize. The depths differ by 2, so we climb u toward v's level, watching each up[0] lookup: up[0][2] = 4 lifts u to depth 3, then up[0][4] = 5 lifts it to depth 2. Now both sit at depth 2, but u is on 5 and v on 15 — different nodes, so the LCA is higher.

Lift together. We jump both up only while it keeps them apart. up[0][5] = 10 and up[0][15] = 14 are different, so we take that jump: u → 10, v → 14. The next jump would be up[0][10] = 12 and up[0][14] = 12 — the same node, which would overshoot, so we skip it. No jump separates them anymore, so their shared parent — node 12 — is the lowest common ancestor.

The code, line by line

LOG = 20
def lca(u, v, depth, up):
    # up[k][x] = 2^k-th ancestor of x
    if depth[u] < depth[v]:
        u, v = v, u
    # 1) lift deeper node u up to depth[v]
    diff = depth[u] - depth[v]
    for k in range(LOG):
        if diff >> k & 1:
            u = up[k][u]
    if u == v:
        return u
    # 2) lift both until just below the LCA
    for k in reversed(range(LOG)):
        if up[k][u] != up[k][v]:
            u = up[k][u]
            v = up[k][v]
    return up[0][u]

• The swap on lines 4–5 guarantees u is the deeper node, so the rest of the function only ever lifts u down to v and then both upward.
• Lines 7–10 close the depth gap. diff >> k & 1 checks bit k of the distance; if it is set, a 2^k jump is part of the climb, so we apply up[k][u].
• Lines 11–12 catch the case where v was an ancestor of u all along — after equalizing, u == v means v is the LCA.
• Lines 14–17 lift both nodes from the highest power down to 2^0, taking a jump only when it keeps them on different ancestors. Going high-to-low is essential: it never overshoots.
• Line 18 returns the common parent — after the loop, u and v are the two distinct children just below the LCA, so up[0][u] is the answer.

Complexity

Each up[k][x] is built from the previous level with up[k][x] = up[k-1][up[k-1][x]] — a 2^k jump is two 2^(k-1) jumps. That recurrence fills the whole table in a single O(n log n) pass before any query.

When to use / pitfalls

Practice