Lowest Common Ancestor

Finding the deepest node that is an ancestor of two given nodes in a tree, with several preprocessing strategies.

The query

The lowest common ancestor (LCA) of two nodes u and v in a rooted tree is the deepest node that is an ancestor of both. LCA queries underlie tree distance, path aggregation, and many tree-algorithm building blocks. The goal is to preprocess the tree so that each query is answered fast.

Binary lifting

Kronos motion — classical

The most common online method precomputes, for each node, its 2^k-th ancestor for all k up to log n. To answer a query, lift the deeper node to the same depth, then lift both nodes together in decreasing powers of two until their parents meet. Preprocessing is O(n log n) and each query is O(log n).

Binary lifting query

python

def lca(u, v, up, depth, LOG):
    if depth[u] < depth[v]:
        u, v = v, u
    diff = depth[u] - depth[v]
    for k in range(LOG):
        if diff & (1 << k):
            u = up[k][u]
    if u == v:
        return u
    for k in reversed(range(LOG)):
        if up[k][u] != up[k][v]:
            u, v = up[k][u], up[k][v]
    return up[0][u]

Euler tour plus RMQ

Recording an Euler tour reduces LCA to a range-minimum query over node depths: the LCA of u and v is the shallowest node between their first appearances. With a sparse table this gives O(n log n) preprocessing and O(1) queries; Tarjan's offline union-find method answers a batch in near-linear time.

Uses

Distance in a tree: depth[u] + depth[v] - 2*depth[lca].
Path queries via heavy-light decomposition.
Ancestor and subtree tests in linear preprocessing.