Lowest Common Ancestor & Binary Lifting

The previous lessons gave us a rooted tree and a single root-to-node path for each vertex. Many problems instead ask about two vertices at once: how far apart are $u$ and $v$? what is the highest fork their paths share? which company contains both of two nested regions? Each reduces to one question: the lowest common ancestor.

The LCA is well defined and unique: the sets of ancestors of $u$ and of $v$ are each a chain from the root, so their intersection is a chain, and a finite chain has a unique deepest element.

The naive walk

If every node stores a parent pointer and a depth, one query is easy. Lift the deeper of $u,v$ until both sit at the same depth, then advance both pointers up in lockstep; the first node they agree on is the LCA.

This needs no preprocessing and is correct, but each step moves up one edge, so a query costs $O(h)$ where $h$ is the tree's height. On a balanced tree $h=O(\log n)$, but on a degenerate path $h=\Theta (n)$, and $q$ queries cost $O(qn)$. We want a query cost that does not depend on shape. (For the asymptotic notation, see asymptotic analysis.)

Binary lifting

The fix is to make each jump cover an exponentially larger distance. Instead of go up one, precompute, for every node $v$ and every $k$, a pointer that goes up $2^k$ edges at once.

The whole table is built from a single doubling identity: climbing $2^k$ edges is climbing $2^{k-1}$ edges twice.

So column $k$ of the table is computed entirely from column $k-1$, one pass per power of two. The number of columns is $K=\lceil {\log }_{2}n\rceil$, since no node has an ancestor more than $n-1$ edges up.

The table has $n(K+1)$ entries and each costs $O(1)$, so preprocessing is $O(n\log n)$ time and $O(n\log n)$ space.

$k$-th ancestor in $O(\log n)$

Any non-negative integer $k$ has a unique binary expansion, so the climb of $k$ edges decomposes into jumps of size $2^0,2^1,2^2,\dots$, one jump per set bit. Take each set bit from low to high and follow the matching column of up.

At most $K+1$ bits are set, so this is $O(\log n)$. The order of the jumps does not matter for the destination (they compose to the same total climb), but processing low bits first keeps the running node well-defined at each step.

LCA in $O(\log n)$

The LCA query reuses the same jumps as two phases. Phase 1 lifts the deeper node up by exactly $depth[u]-depth[v]$, a single $\text{Kth-Ancestor}$ call, so $u$ and $v$ sit at equal depth. If they now coincide, one was an ancestor of the other and we are done. Phase 2 lifts both nodes simultaneously: scanning $k$ from high to low, we jump both up by $2^k$ only when that keeps them distinct. When the loop ends, $u$ and $v$ are the two distinct children-side nodes just below the LCA, so the answer is their common parent.

The depth-equalizing jump is $O(\log n)$ and the second loop runs $K+1$ times, so each LCA query is $O(\log n)$ after the one-time $O(n\log n)$ build.

Here $u$ and $v$ already share depth; both lift to $c$ and $b$ (kept distinct), then one parent step lands on $a=\mathrm{lca}(u,v)$, drawn in acc.

A worked table

The whole method lives in the up grid. For the small tree below, rows are nodes and columns are $k=0,1,2$, with each entry the $2^k$-th ancestor. Column $0$ is the parent; every later column is the previous column composed with itself.

Reading row $8$: its $1$st ancestor is $4$ ($k=0$), its $2$nd is $2$, its $4$th is $1$. To find the $5$th ancestor of $8$ we write $5=101_2$ and jump by the $k=0$ and $k=2$ columns — cells highlighted in acc — climbing $1$ then $4$ edges; on this depth-$3$ tree that runs off the root, which $\text{Kth-Ancestor}$ reports as nil.

Application: tree distance and path queries

LCA turns a two-vertex path question into arithmetic on depths. The unique path from $u$ to $v$ in a tree goes up from $u$ to $\mathrm{lca}(u,v)$ and back down to $v$, so its length is

Each query is one LCA plus $O(1)$ work, hence $O(\log n)$. The same decomposition answers is $w$ on the $u-v$ path?, aggregates a value along the path (split into the two vertical legs), or, combined with $\text{Kth-Ancestor}$, emits step-by-step U/L/R directions: climb $depth[u]-depth[\text{lca}]$ steps up, then walk the recorded downward path to $v$.

Alternatives

Binary lifting is the most broadly useful LCA method, but two others are worth knowing.¹

• Euler tour + sparse-table RMQ. Record the Euler traversal of the tree (each node appended on entry and after each child returns); within it, the LCA of $u$ and $v$ is the shallowest node visited between any occurrence of $u$ and of $v$. That reduces LCA to a range-minimum query over the depth array, which a sparse table answers in $O(1)$ after an $O(n\log n)$ build.² So queries drop to $O(1)$, but the structure is static and does not directly give $k$-th ancestors.
  The reduction is best seen laid out. Below the tree, the Euler tour writes each node as it is entered and re-entered, with its depth underneath. The LCA of $u$ and $v$ is the shallowest entry anywhere between an occurrence of $u$ and one of $v$ — i.e. the minimum of that depth subarray (shaded), which here is $a$:

• Tarjan's offline LCA. If all query pairs are known in advance, a single DFS with a union-find structure answers them in near-linear $O((n+q)\alpha )$ total time, processing each query when its second endpoint is first reached.³

Takeaways

• The lowest common ancestor of $u$ and $v$ is the deepest node ancestral to both; it is unique because ancestor sets are root-chains.
• The naive walk (equalize depth, climb together) needs no preprocessing but costs $O(h)$ per query, or $\Theta (n)$ on a degenerate tree.
• Binary lifting precomputes $up[v][k]$, the $2^k$-th ancestor, via the doubling identity $up[v][k]=up[up[v][k-1]][k-1]$ in $O(n\log n)$ time and space.
• A $k$-th-ancestor query jumps by each $1$-bit of $k$; an LCA query lifts the deeper node to equal depth, then jumps both up by decreasing powers of two while they stay distinct — each $O(\log n)$.
• Tree distance is $depth[u]+depth[v]-2depth[\mathrm{lca}(u,v)]$, turning path queries into $O(\log n)$ arithmetic.
• Alternatives: Euler tour + sparse-table RMQ gives $O(1)$ queries on a static tree; Tarjan's union-find DFS answers all queries offline in near-linear time. Binary lifting wins on being online and also serving $k$-th ancestors.