Lowest Common Ancestor Visualization | Binary Lifting vs Naive Walk

The idea: the deepest ancestor two nodes share

In a rooted tree, the lowest common ancestor LCA(u, v) is the deepest node that has both u and v below it. A node counts as its own ancestor, so if v is above u, the answer is v. LCA queries answer "how far apart are these two nodes" (dist = depth(u) + depth(v) − 2·depth(LCA)), "which version did these two branches fork from", and many tree problems in contests. The page uses one tree of 16 nodes, root 0, depth up to 6, and answers queries two ways: walking up one parent at a time, and binary lifting, which jumps by powers of two using a precomputed table.

The page's tree of 16 nodes. The paths from 15 and from 14 go up separate branches and first meet at the root 0, so LCA(15, 14) = 0. The paths from 15 and from 8 first meet at node 1, so LCA(15, 8) = 1. — Follow both nodes up: the first node on both paths is the LCA. LCA(15, 14) = 0 and LCA(15, 8) = 1.

The naive walk

Walk the deeper node up, one parent at a time, until both nodes have the same depth. Then walk both up together until they are the same node. That node is the LCA. It needs nothing but the parent and depth of each node, and it costs one step per level: O(depth) per query. On a tree shaped like a long path that is O(n), so 10⁵ queries on a tree of 10⁵ nodes take about 10¹⁰ steps. (Demo: naive walk vs binary lifting on LCA(15, 14): 11 single steps.)

The up[k][v] table

Binary lifting stores, for every node v and every k, up[k][v] = the ancestor 2^k levels above v. Row 0 is the parent array. Every other row comes from the row above it, because a jump of 2^k is two jumps of 2^k−1:

up[0][v] = parent(v)            (parent(root) = root)
up[k][v] = up[k-1][ up[k-1][v] ]

With LOG = ⌈log₂(max depth + 1)⌉ rows (4 here: jumps of 1, 2, 4 and 8), the table costs O(n log n) time and memory, once. A jump past the root stays at the root, so the table never needs a "no ancestor" value. (Demo: build the up[k][v] table)

The path from node 15 to the root: 15, 13, 10, 7, 3, 1, 0. Arcs show up[0][15] = 13 (1 up), up[1][15] = 10 (2 up), up[2][15] = 3 (4 up), and up[3][15] = 0 (8 up, past the root, so it stays at 0). The 4-up arc is built from two 2-up arcs: 15 to 10 and 10 to 3. — Each row doubles the jump: 4 up from 15 is 2 up to 10, then 2 up again to 3.

Step 1: lift the deeper node

Make u the deeper node. The depth difference d is a sum of powers of two: its binary digits. For each 1 bit k, jump u = up[k][u]. Now u and v have the same depth, in at most LOG jumps instead of d steps. For LCA(15, 8), d = 3 = 011₂: a jump of 2 (15 → 10) and a jump of 1 (10 → 7). (Demo: LCA(15, 8)) If u lands on v, then v was an ancestor of u and is the answer: LCA(15, 3) needs a single jump of 4. (Demo: LCA(15, 3))

Step 2: lift both

Now u ≠ v at the same depth. Try k from LOG − 1 down to 0. If up[k][u] ≠ up[k][v], the two ancestors are still on different branches, so the LCA is higher up: jump both. If they are equal, that node is a common ancestor, but maybe not the lowest one, so do not jump. This is a binary search on "how far below the LCA are we": after k = 0, u and v are the two children of the LCA on their paths, and the answer is up[0][u].

For LCA(15, 14): the lift brings 15 to 13. Then k = 3 gives 0 and 0 (skip), k = 2 gives 1 and 2 (jump both), k = 1 and k = 0 give 0 and 0 (skip). u = 1, v = 2, and the LCA is up[0][1] = 0. (Demo: LCA(15, 14))

if depth[u] < depth[v]: swap(u, v)
d = depth[u] - depth[v]
for k in LOG-1 down to 0: if d & (1 << k): u = up[k][u]
if u == v: return u
for k in LOG-1 down to 0:
    if up[k][u] != up[k][v]: u, v = up[k][u], up[k][v]
return up[0][u]

Cost

method	preprocessing	per query	memory
naive walk	depths, O(n)	O(depth), up to O(n)	O(n)
binary lifting	O(n log n)	O(log n)	O(n log n)
Euler tour + sparse table	O(n log n)	O(1)	O(n log n)
Tarjan's offline LCA	all queries known first	about O(1) each, with union-find	O(n)

Binary lifting is the usual choice because the same table also answers "the k-th ancestor of v" in O(log n), and it extends to path maximums or sums by storing a second value next to each up[k][v]. The depths come from one depth-first search from the root. The tree here is a general rooted tree; in a binary search tree the LCA can also be found from the keys alone, and Tarjan's offline method uses disjoint sets.

What the page leaves out

The tree is fixed at 16 nodes and the table is built by rows, not by the usual DFS that fills up[·][v] when v is first visited. The page leaves out the Euler tour + range-minimum reduction, Tarjan's offline algorithm, the O(n) / O(1) Farach-Colton and Bender method, k-th ancestor and path-aggregate queries, LCA in a forest, and trees that change (link-cut trees).