Understanding Binary Lifting: ... Note

Understanding Binary Lifting: Finding Ancestors Efficiently in Trees

Binary Lifting is an efficient technique for finding ancestors in a tree by precomputing information. Instead of traversing one level at a time, it allows for jumps of distances that are powers of two, such as 1, 2, 4, or 8 levels. This significantly reduces query time from O(K) to O(log K) for finding the Kth ancestor. The precomputation involves calculating the ancestor at 2^j levels for each node, using the formula up[node][j] = up[up[node][j-1]][j-1]. The space and time complexity for this preprocessing is O(N log N), where N is the number of nodes. To find the Kth ancestor, K is represented in binary, and jumps are made corresponding to the set bits in its binary representation. Binary Lifting can also be used to efficiently find the Lowest Common Ancestor (LCA) of two nodes. This involves first ensuring both nodes are at the same depth by moving the deeper node upwards, then simultaneously moving both nodes upwards using binary jumps until they are just below their LCA. The parent of either node at that point is the LCA. This LCA finding process also takes O(log N) time after the initial O(N log N) preprocessing.
CdXz5zHNQW_EhFBJeaHh4.webp