Finding a meeting point
The lowest common ancestor of two nodes is the deepest node that is an ancestor of both. Binary lifting answers such queries quickly after a one time preprocessing pass, by precomputing each node's ancestor at every power of two distance above it.
Precomputed jump table
Build a table where one entry gives, for each node, its ancestor two to the kth steps up. The base case is the direct parent. Each higher entry is filled by doubling: the ancestor two to the kth steps up is the ancestor that many steps above the ancestor two to the k minus one steps up. Filling the table touches each node for each power of two, so preprocessing is the node count times a logarithm.
Answering a query
- First equalize depth: lift the deeper node up using power of two jumps until both nodes sit at the same depth.
- Then lift together: jump both nodes up by the largest power of two that keeps them on different ancestors, repeating down to one. The node just above where they meet is their lowest common ancestor.
Key idea
Precompute ancestors at every power of two distance, then answer each lowest common ancestor query by depth matching and synchronized jumps in logarithmic time.