Lowest Common Ancestor by Binary Lifting

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.

Experiment

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

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