Lowest Common Ancestor (Binary Lifting)

The Lowest Common Ancestor of nodes u and v in a rooted tree is the deepest node that is an ancestor of both. Binary lifting precomputes for every node its 2^k-th ancestor for every power of two, reducing each LCA query to O(log n) — a workhorse for path queries, tree distances, and dynamic tree algorithms.

Preprocessing: DFS + Lifting Table

A DFS from the root fills parent[] and depth[]. The lifting table is then:

up[0][v] = parent[v]
up[k][v] = up[k−1][up[k−1][v]]     # 2^k-th ancestor = 2^(k−1) twice

That double-jump is the whole trick: taking 2^(k−1) steps twice is 2^k steps, and each row is O(n), for O(n log n) total.

Query: Lift, Then Climb

lca(u, v):
  if depth[u] < depth[v]: swap(u, v)
  for k = LOG..0:                 # 1) equalize depths
    if depth[u] − depth[v] has bit k: u = up[k][u]
  if u == v: return u
  for k = LOG..0:                 # 2) climb together
    if up[k][u] != up[k][v]:
      u = up[k][u]; v = up[k][v]
  return up[0][u]                 # one step below the LCA

Phase 1 lifts the deeper node by the depth difference, decomposed into powers of two. Phase 2 climbs both nodes as high as possible without reaching a common ancestor, so they end one level below the LCA — whose parent is the answer.

What It Unlocks

• Tree distance: dist(u,v) = depth[u] + depth[v] − 2·depth[lca(u,v)].
• Path queries: split the u→v path at the LCA and aggregate each half.
• Ancestor tests: isAncestor(a, b) iff the LCA is a (plus Euler-tour ordering).
• K-th ancestor: exactly the lifting table, in O(log n).
• Heavy-lifting for advanced topics: HLD, centroid decomposition, and tree DP.

Practice Trajectory

1. Build parent[], depth[], and up[][] for a small tree and verify each row by hand.
2. Implement lca, then dist(u, v).
3. Implement kthAncestor(v, k) using the same table.
4. Compute path sums/min along u→v by splitting at the LCA.
5. Solve: LCA on sparse and dense trees, and dynamic LCA with incremental inserts.

When It’s the Right Tool