The lowest common ancestor
The lowest common ancestor of two nodes is the deepest node that is an ancestor of both. Walking up one step at a time is slow on deep trees, so we precompute jumps of growing size.
Binary lifting
Precompute, for every node, its ancestor that is one step up, two steps up, four steps up, and so on in powers of two. Each such ancestor is found by combining two smaller jumps that are already known. This sparse table is built once over the whole tree.
Answering a query
To find the ancestor shared by two nodes:
- First lift the deeper node up until both nodes sit at the same depth.
- Then lift both nodes together by the largest jumps that keep them apart.
- When no jump moves them apart, their parent is the answer.
Because depths and gaps are written in binary, a handful of power of two jumps cover any distance. Each query resolves in time that grows only with the logarithm of the tree height.
Key idea
Store each node's ancestors at power of two distances so two nodes can be raised to a shared ancestor with a few binary jumps.