Lowest Common Ancestor by Binary Lifting

Concept Overview

The Lowest Common Ancestor (LCA) of two nodes u and v in a tree is the lowest node that has both u and v as descendants. Binary lifting efficiently answers LCA queries by precomputing an ancestor table, where up[u][j] stores the 2^j-th ancestor of u.

Worked Example

Consider a Balanced Tree with vertices 0 to 6. The parents array is [0, 0, 0, 1, 1, 2, 2]. Let's find the LCA of u = 4 and v = 5 independently by path intersection.

Find the path from the root to u=4: [0, 1, 4].
Find the path from the root to v=5: [0, 2, 5].
The common ancestors are the nodes present in both paths. The only common ancestor is 0.
Therefore, the LCA is 0.

The distance in edges between u and v is the sum of the distances from u to the LCA and v to the LCA: 2 + 2 = 4. The query path is [4, 1, 0, 2, 5].

Experiment

You can interactively trace the binary lifting algorithm in the Lowest Common Ancestor module.

Select Tree as "Balanced".
Set Vertex u to "4".
Set Vertex v to "5".
Click Step to see the depth equalization phase. Since both nodes are at depth 2, no jumps are made initially.
Continue Step through the three depth tests, then observe the simultaneous jump tests j=2,1,0.
Click Finish to reveal the final result: LCA is 0, distance is 4, and the path is [4,1,0,2,5].

Limitations

The binary lifting implementation assumes a valid rooted tree structure with no cycles. It does not parse or support general directed cyclic graphs. The interactive visualization is limited to exactly 7 vertices (0 to 6) to keep the trace length bounded to at most 8 events, facilitating a step-by-step educational breakdown.

References

The binary lifting technique and ancestor table structure are based on the standard competitive programming approach documented at:
Lowest Common Ancestor - Binary Lifting (CP-Algorithms).

Lowest Common Ancestor by Binary Lifting