Chapter 10 · Lowest Common Ancestor
The LCA Problem
What the lowest common ancestor is, the seven distances it answers, and how to choose among four algorithms.
Definition
Root the tree at r. The lowest common ancestor lca(u,v) is the deepest vertex that is an ancestor of both. It is the unique vertex where the paths r → u and r → v stop agreeing, and the junction of the three paths u, v, r.
Everything one LCA answers
- dist(u,v) = depth(u) + depth(v) - 2depth(lca),
- dist on an edge-weighted tree: same formula with prefix sums from the root,
- the k-th vertex on the path u ⇝ v (walk up from u, then from v — LCA by Binary Lifting),
- lca of a set S (the "virtual tree" root) = the vertex minimising ∑x ∈ S dist(x, y) over S's Steiner closure — computed from lca of the min- and max-tin elements (Virtual Trees),
- whether u is an ancestor of v: lca(u,v) = u, or the cheaper
tin/touttest (Entry/Exit Times and the Euler Tour), - "jump j steps up from v", "the node just below the LCA on the path", "the centroid of a path",
- subtree-union queries: lca gives the boundary vertex, then a Fenwick Tree (Binary Indexed Tree) over
tingives the count.
#Choosing an algorithm
| method | preprocess | query | memory | offline? | notes |
|---|---|---|---|---|---|
| naive climb | O(n) | O(n) worst | O(n) | — | fine on balanced trees; a path graph kills it |
| binary lifting | O(n log n) | O(log n) | O(n log n) | no | the default; also does "jump k steps" |
| Euler tour + sparse table | O(n log n) | O(1) | O(n log n) | no | LCA via Range Minimum Query |
| Euler tour + ±1 RMQ (Bender–Farach-Colton) | O(n) | O(1) | O(n) | no | LCA via Range Minimum Query, the "too clever" row |
| Tarjan offline | — | O(n + q α) total | O(n+q) | yes | Tarjan's Offline LCA; DSU only |
| Heavy-light | O(n log n) or O(n) | O(log n) | O(n) | no | pays off when you need path aggregates anyway (Heavy-Light Decomposition) |
NoteThe honest recommendation
Write binary lifting. It is 12 lines, never wrong, gives you k-th ancestor for free, and O(n log n) with n = 2 × 105 is 3.6 million integers — 14 MB, well inside any limit. Move to O(1) RMQ only when q ≥ 106 and the constant actually shows up in the clock, or to Tarjan when the queries are offline and you already have DSU in the solution.
#Two conventions that decide your code's shape
Pick once, write in a comment
- root: fix r = 0 (or 1) and never change it; "depth" is measured from it,
- lca(v,v) = v — the identity case must be handled by the algorithm, not by an
ifat the call site, - 0-indexed up[v][0] = parent(v), with parent(r) = r (self-loop at the root) is the least error-prone: it makes lifting past the root idempotent instead of returning -1 that you must check everywhere,
- log bound:
LOG = __lg(n) + 1(or 20 for n ≤ 106, 19 for 105… compute it, don't guess), - forest: if the input is not connected, LCA is undefined across components — either assert same-component with DSU first, or add a super-root (which makes every pair comparable and often simplifies the code).