Lowest Common Ancestor (Binary Lifting)

What the lowest common ancestor is

Root a tree at some node r. Node a is an ancestor of node v if a lies on the unique path from r to v — and by convention every node is an ancestor of itself. The lowest common ancestor of u and v, written LCA(u, v), is the ancestor common to both that is deepest — farthest from the root.

Two clean ways to think about it:

• Path meeting point. Walk from the root toward u and from the root toward v simultaneously. The two walks share a common prefix and then split. The last shared node is the LCA.
• Deepest common ancestor. Among all nodes that are ancestors of both u and v, pick the one with maximum depth. It is unique, because the set of common ancestors is exactly the set of ancestors of that one node.

Special case worth internalizing: if u is an ancestor of v, then LCA(u, v) = u — a node is its own ancestor. Every correct algorithm must return u here rather than u's parent.

Why LCA matters

The LCA is the hinge of the tree path between two nodes. The unique path from u to v goes up to LCA(u, v) and then down again, so once you can find the LCA quickly, a whole family of tree queries collapses to O(log n):

• Node distance. The number of edges between u and v is depth[u] + depth[v] − 2·depth[LCA(u, v)]. For weighted trees, swap depth for root distance.
• Path aggregates. Sum, min, max, or XOR along the u–v path — decompose into the two upward legs and combine.
• Kth ancestor / kth node on a path. The same jump pointers used for LCA answer "what is the k-th ancestor of v" in O(log n).
• Heavy-light and centroid decompositions use LCA as a primitive when routing path queries.
• Phylogenetics and version control. The LCA of two taxa in a species tree is their most recent common ancestor; the merge-base of two commits in Git is an LCA in the commit DAG's spanning tree.

How binary lifting works

Binary lifting is built on one observation: any ancestor jump of length d can be decomposed into jumps whose lengths are powers of two — exactly the set bits of d in binary. So if we can jump by 1, 2, 4, 8, … levels in O(1) each, we can reach any of the up-to-n ancestors in at most ⌈log₂n⌉ hops.

The precomputed table is a 2-D array:

• up[v][0] = the direct parent of v (the root's parent is a sentinel, e.g. −1 or the root itself).
• up[v][k] = the 2ᵏ-th ancestor of v, computed as up[ up[v][k−1] ][k−1] — jump 2ᵏ⁻¹ levels, then 2ᵏ⁻¹ more.

Filling the table for all n nodes and all LOG = ⌈log₂n⌉ levels is O(n log n) time and O(n log n) space. A single DFS also records each node's depth.

A query LCA(u, v) has two phases:

1. Depth equalization. Assume without loss of generality that u is at least as deep as v. Lift u up by depth[u] − depth[v] levels using the set bits of that difference. Now both nodes sit at the same depth. If u == v, that node is the LCA (one was an ancestor of the other) — return it.
2. Synchronized ascent. For k from LOG down to 0, if up[u][k] ≠ up[v][k], jump both: u = up[u][k]; v = up[v][k]. Testing the largest safe jumps first means we ascend as far as possible without overshooting the LCA. When the loop ends, u and v are distinct children of the LCA, so up[u][0] is the answer.

Why the ascent stops one level below the LCA: at the LCA and above, up[u][k] and up[v][k] become equal, so we never jump there; strictly below the LCA they differ, so we always do. The loop leaves both nodes as far up as possible while still distinct — exactly the LCA's children.

The Euler tour + RMQ alternative

There is a completely different, and asymptotically better, route to LCA: reduce it to a range-minimum query (RMQ) over an Euler tour.

Run a DFS and append the current node to a list on entry and every time you return to it after finishing a child. This Euler tour has length exactly 2n − 1 and lists every node, alongside its depth. Record first[v], the index of v's first appearance. Then:

LCA(u, v) is the node of minimum depth in the Euler-tour segment between first[u] and first[v].

Intuitively, going from u to v in the tour forces the DFS to climb up to their common ancestor and no higher, so the shallowest node in that window is precisely the LCA. That is a range-minimum query on the depth array. Answer it with a sparse table for O(1) queries after O(n log n) preprocessing, or exploit that consecutive Euler-tour depths differ by exactly ±1 — the ±1 RMQ trick — to reach O(n) preprocessing and O(1) queries.

Binary lifting vs other LCA methods

	Binary lifting	Euler + sparse-table RMQ	Euler + ±1 RMQ	Tarjan offline (union-find)
Preprocessing	O(n log n)	O(n log n)	O(n)	O(n + q · α(n))
Query	O(log n)	O(1)	O(1)	Amortized ~O(α(n))
Space	O(n log n)	O(n log n)	O(n)	O(n)
Online?	Yes	Yes	Yes	No — needs all queries up front
Gives k-th ancestor?	Yes, for free	No	No	No
Ease of implementation	Easy	Easy	Hard (block decomposition)	Medium
Best for	Online queries, path/k-th-ancestor combos	Many online LCA queries	Tightest asymptotics	All queries known in advance

In practice binary lifting is the default: it is short to write, cache-friendly enough, and the jump table doubles as a k-th-ancestor structure. The theoretically optimal ±1 RMQ (Bender–Farach-Colton, 2000) wins only when the O(log n) query factor genuinely matters and you are willing to implement the block decomposition.

How it works in Python

import math

class LCA:
    def __init__(self, n, adj, root=0):
        self.n = n
        self.LOG = max(1, math.ceil(math.log2(n)))
        self.up = [[-1] * n for _ in range(self.LOG)]   # up[k][v] = 2^k-th ancestor
        self.depth = [0] * n
        self._dfs(adj, root)
        self._build()

    def _dfs(self, adj, root):
        # Iterative DFS to fill up[0] (direct parents) and depth.
        stack = [(root, -1)]
        while stack:
            v, parent = stack.pop()
            self.up[0][v] = parent
            for w in adj[v]:
                if w != parent:
                    self.depth[w] = self.depth[v] + 1
                    stack.append((w, v))

    def _build(self):
        for k in range(1, self.LOG):
            for v in range(self.n):
                mid = self.up[k - 1][v]
                self.up[k][v] = self.up[k - 1][mid] if mid != -1 else -1

    def kth_ancestor(self, v, k):
        for i in range(self.LOG):
            if v == -1:
                break
            if k >> i & 1:
                v = self.up[i][v]
        return v

    def query(self, u, v):
        # 1) Equalize depths — lift the deeper node.
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        u = self.kth_ancestor(u, self.depth[u] - self.depth[v])
        if u == v:
            return u                      # one was an ancestor of the other
        # 2) Synchronized ascent — largest jumps first.
        for k in range(self.LOG - 1, -1, -1):
            if self.up[k][u] != self.up[k][v]:
                u = self.up[k][u]
                v = self.up[k][v]
        return self.up[0][u]              # both are now children of the LCA

    def distance(self, u, v):
        return self.depth[u] + self.depth[v] - 2 * self.depth[self.query(u, v)]

The kth_ancestor helper reuses the same jump table for depth equalization, so there is no separate lifting code. Note the two loop directions: k-th ancestor reads the set bits of k low-to-high, while the synchronized ascent tries the biggest jumps first — both are correct, and both touch at most LOG entries.

A worked query

Take a tree rooted at node 0 with edges 0–1, 0–2, 1–3, 1–4, 4–7, 2–5, 2–6. Depths: 0 at 0; 1 and 2 at depth 1; 3, 4, 5, 6 at depth 2; 7 at depth 3.

Query LCA(7, 6). Node 7 has depth 3, node 6 has depth 2. Equalize: lift 7 by 3 − 2 = 1 level → parent 4. Now compare 4 (depth 2) and 6 (depth 2); they differ. Synchronized ascent: the k=1 jump from both (2ⁱ = 2 levels) lands both at 0 — equal, so skip it. The k=0 jump gives up[4][0]=1 and up[6][0]=2 — different, so jump: 4→1, 6→2. Loop ends; return up[1][0] = 0. So LCA(7, 6) = 0, and their distance is 3 + 2 − 2·0 = 5 edges. Trace the tree — 7→4→1→0→2→6 — and there are indeed five edges.

Common misconceptions and pitfalls

• Skipping depth equalization. The synchronized ascent only converges when both nodes start at equal depth. Run it on unequal depths and the paired jumps drift past the true LCA.
• Returning the wrong node when one is an ancestor of the other. After equalization, if u == v you must return that node immediately. Falling through to the ascent loop and then to up[u][0] would return the LCA's parent — off by one.
• Ascending in the wrong order. The synchronized ascent must try the largest jumps first (k from high to low). Small-to-large can overshoot: a big early jump might already pass the LCA, and you can't undo it.
• LOG too small. You need LOG ≥ ⌈log₂n⌉, i.e. enough levels to represent the maximum possible depth (a path graph has depth n−1). One level short silently truncates deep jumps.
• Recursion-depth overflow. A recursive DFS on a path-like tree of 10⁵–10⁶ nodes blows the call stack in Python and default-stack C++. Use an iterative DFS or raise the limit.
• Forgetting sentinels. When a jump goes past the root, up[v][k] must be a sentinel (−1). If up[v][k−1] is already the sentinel, up[v][k] is too — don't index with −1.
• Assuming LCA needs a rooted tree you already have. "Lowest" is only meaningful relative to a chosen root; re-rooting changes the answer. Fix the root before any query.

A note on history

The complexity question — can LCA be answered in constant time per query after linear preprocessing? — was first studied by Alfred Aho, John Hopcroft, and Jeffrey Ullman in 1973, who solved important special cases. Harel and Tarjan gave the first general O(n)-preprocessing, O(1)-query algorithm in 1984; Schieber and Vishkin simplified it in 1988. Berkman and Vishkin, and later Bender and Farach-Colton (2000), reduced LCA to ±1 RMQ, giving the clean linear-time solution taught today. Binary lifting itself — doubling jump pointers — is folklore descended from the same power-of-two doubling idea behind sparse tables and pointer-jumping, and remains the most implemented method because of its simplicity and its bonus k-th-ancestor capability.