Binary Lifting: Jumping Up a Tree in Logarithmic Time

The core idea: powers of two as a jump table

Every non-negative integer k has a unique binary representation, so k can be written as a sum of distinct powers of two. Binary lifting exploits this on a rooted tree: instead of storing only each node's immediate parent, we store, for every node v and every exponent j, the ancestor of v that lies exactly 2ʲ levels above it. That single 2-D table — call it up[v][j] — is the entire data structure.

The governing invariant is short and exact:

• up[v][0] = the immediate parent of v (or a sentinel −1 if v is the root),
• up[v][j] = up[ up[v][j-1] ][j-1] for j ≥ 1 — the 2ʲ-th ancestor is the 2ʲ⁻¹-th ancestor of the 2ʲ⁻¹-th ancestor.

That recurrence is the whole trick: a jump of length 2ʲ is two chained jumps of length 2ʲ⁻¹. Because each entry depends only on entries with a smaller j, you fill the table column by column (all j = 0, then all j = 1, …) in a bottom-up pass. The maximum useful exponent is LOG = ⌈log₂ n⌉, since no ancestor is more than n − 1 levels up. Binary lifting is a textbook application of dynamic programming on a sparse table, closely related to the sparse-table structure used for range-minimum queries.

Building the table step by step

Assume the tree is given as an adjacency list and rooted at node 0. First a DFS (or BFS) records each node's depth and its immediate parent into column 0. Then a simple double loop fills the remaining columns.

LOG = ceil(log2(n))
for v in 0..n-1: up[v][0] = parent[v]   // -1 for root
for j in 1..LOG-1:
    for v in 0..n-1:
        mid = up[v][j-1]
        up[v][j] = (mid == -1) ? -1 : up[mid][j-1]

The order matters: the outer loop is over the exponent j, the inner over nodes v. When we compute column j, every entry in column j − 1 is already final, so the recurrence reads only settled values. If you accidentally swap the loops and iterate j innermost per node, you read column j − 1 for an ancestor that may not be computed yet — a classic off-by-structure bug.

• Sentinel discipline: use −1 (or n as an out-of-range index) for "above the root." Any jump landing on the sentinel stays the sentinel, so over-jumping is harmless and self-correcting.
• Depth is mandatory for LCA: store depth[v] during the initial traversal; the LCA routine needs it to equalize levels.
• 1-based vs 0-based: pick one and be consistent — the single most common source of wrong answers in contest submissions is a root indexed inconsistently between parent and up.

Querying: k-th ancestor and lowest common ancestor

To find the k-th ancestor of v, walk the set bits of k. For each bit j that is 1 in k, jump v up by 2ʲ using the table; the surviving node is the answer (or −1 if the walk falls off the root).

function kth_ancestor(v, k):
    for j in 0..LOG-1:
        if (k >> j) & 1:
            v = up[v][j]
            if v == -1: return -1
    return v

Because k has at most LOG bits, this loop performs at most ⌈log₂ n⌉ jumps — O(log n). LCA builds directly on this in two phases:

• Level the deeper node. If depth[u] > depth[v], lift u by exactly (depth[u] − depth[v]) using kth_ancestor, so both nodes sit at the same depth. If they're now equal, that node is the LCA.
• Binary-search the divergence point. Iterate j from LOG−1 down to 0; whenever up[u][j] ≠ up[v][j], jump both up by 2ʲ. This lifts u and v as high as possible while they remain in different subtrees. After the loop, u and v are distinct children of the LCA, so up[u][0] is the answer.

The descending-j order is essential: it greedily consumes the largest safe jump first, guaranteeing the pair stops one step below the true ancestor. Total work is one leveling pass plus one bit-scan — O(log n) per query, with tiny constants (a shift, a compare, an array read).

Complexity and why it's optimal for this shape

Preprocessing time: the table has n rows and LOG = ⌈log₂ n⌉ + 1 columns, each entry computed in O(1) from one lookup — Θ(n log n) total. The DFS that seeds column 0 is O(n), dominated by the fill. Space: Θ(n log n) for the table; this is the price you pay to buy fast queries. For n = 10⁶ that's roughly 20 × 10⁶ integers ≈ 80 MB as 32-bit ints — the dominant practical cost and the reason people reach for the Euler-tour + RMQ variant when memory is tight.

Query time: both k-th ancestor and LCA are O(log n) worst case, independent of tree shape — a bamboo (single chain of depth n) is exactly as fast as a balanced tree. That's the whole point: the naive parent walk is O(depth), which degrades to Θ(n) on a chain; binary lifting flattens that to Θ(log n) by paying the one-time Θ(n log n) build.

• Break-even: if you issue q queries, total cost is Θ(n log n + q log n). Binary lifting wins over the naive walk once q · depth exceeds the build, which is essentially always for many queries on deep trees.
• Constant factors: queries are branch-light and cache-reasonable when up is stored row-major with j contiguous; the build is the memory-bandwidth-bound part.
• Relative to Θ(1)-query Euler-tour RMQ, binary lifting trades a log factor per query for a smaller constant, trivial implementation, and the bonus of k-th-ancestor and path-aggregate queries the RMQ approach can't do.

Beyond ancestors: path aggregates and functional graphs

The same doubling scheme carries any associative function along the jump, not just the ancestor pointer. Store, alongside up[v][j], a value agg[v][j] that aggregates the edges on the 2ʲ-length path from v upward — min, max, sum, or gcd of edge weights. The build recurrence combines the two halves: agg[v][j] = f(agg[v][j-1], agg[up[v][j-1]][j-1]). Then min-weight-on-path(u, v) is answered by aggregating during the LCA walk in O(log n). This is a standard trick for offline min-cost-to-LCA and Kruskal-reconstruction-tree bottleneck queries.

Binary lifting also generalizes past trees to any functional graph — a graph where every node has exactly one outgoing edge (a successor array). There up[v][j] is "apply successor 2ʲ times," letting you compute the state after k steps in O(log k). Applications include:

• Iterating a permutation or a state machine k times (k up to 10¹⁸) without cycle-length reasoning.
• Fast ancestor-at-level queries in tries and suffix-tree-style structures.
• Finding the node reached after k moves in games or the k-th successor in a linked structure — the doubling replaces Floyd/Brent cycle detection when you only need lookups.

The reason it all works is that the underlying operation (function composition) is associative, so 2ʲ compositions equal two chained 2ʲ⁻¹ compositions — the identical algebra behind fast exponentiation.

Where it's used, and the alternatives it beats

Binary lifting is the default LCA and k-th-ancestor technique in competitive programming: it appears in essentially every ICPC/Codeforces template library, and the LeetCode problem "Kth Ancestor of a Tree Node" (1483) is a direct implementation with q up to 5×10⁴ over n up to 5×10⁴. The Kactl template library and AtCoder's live-broadcast library ship it as a primitive (the official AtCoder Library, ACL, notably has no tree/LCA module). Beyond contests, doubling tables show up wherever a static hierarchy is queried repeatedly:

• Version control & build graphs: ancestor / merge-base style queries over an append-mostly DAG or spanning tree benefit from precomputed jump pointers.
• Phylogenetics and taxonomy: "most recent common ancestor" of two species/nodes in a fixed tree is exactly LCA.
• Compilers: dominator-tree and loop-nesting queries lift the same idea; the classic Θ(1)-LCA machinery is a cousin.

The two main rivals: Euler-tour + sparse-table RMQ gives O(1) LCA (better when queries vastly outnumber nodes and you never need k-th ancestor), and Tarjan's offline LCA with union-find runs in near-linear O((n + q) α(n)) but requires all queries in advance. Binary lifting wins when you want a small, online, general tool that also does k-th ancestor and path aggregates. When the tree itself changes (edge insertions, re-rooting, path updates), you move up to Euler-tour trees or link-cut trees, since binary lifting assumes the tree is static.

Pitfalls, edge cases, and variants

Binary lifting is short but has a handful of reliable traps:

• LOG too small. If ⌈log₂ n⌉ is under-sized (e.g. hardcoded 20 for n > 2²⁰), the deepest jumps silently truncate and k-th-ancestor returns garbage. Set LOG = 1 while (1 << LOG) < n, then add 1 — or just use 25/30 for safety at n ≤ 10⁷/10⁹.
• Root sentinel handling. Every jump must short-circuit on −1. Forgetting the guard reads up[-1][…] (out of bounds) or, with an n-index sentinel, silently wraps — both produce wrong LCAs near the root.
• Depth mismatch bug. In LCA, you must level the deeper node before the descending-j divergence loop, and you must not jump past equal depth. If u and v have equal depth but the naive check for "already equal" is skipped, the divergence loop still returns the correct parent — but only because up[u][0] is taken afterward; test the u == v early-exit explicitly.
• Forests. With multiple roots, give each a distinct sentinel or a virtual super-root; two nodes in different trees have no LCA and the walk must report that (both reach −1).
• Memory. The Θ(n log n) table can dominate; if you only need tree LCA (not k-th ancestor) and memory is tight, prefer the Euler-tour RMQ layout or Sqrt-decomposition of ancestors.

A useful variant: iterative vs recursive build. A recursive DFS to seed depths can stack-overflow on a bamboo of depth 10⁶ — use an explicit stack or BFS for the initial pass. And for dynamic depths where nodes are added at the leaves only, you can extend the table incrementally, computing new rows on insertion in O(log n) each — a lightweight persistent-ancestor structure without rebuilding.

Ancestor / LCA query approaches on a static rooted tree of n nodes

Method	Preprocess	Per query	Extra space	Notes
Naive parent walk	O(n)	O(depth) = O(n) worst	O(n)	No preprocessing; kills you on deep chains
Binary lifting	Θ(n log n)	O(log n)	Θ(n log n)	Simple, supports k-th ancestor + LCA + path aggregates
Euler tour + sparse-table RMQ	Θ(n log n)	O(1)	Θ(n log n)	O(1) LCA but no k-th ancestor; larger constant
Tarjan offline (union-find)	O((n+q) α(n))	amortized α(n)	O(n)	Offline only; all queries known up front
Heavy-light / Euler tour tree	O(n)	O(log n)	O(n)	Handles path updates; heavier to implement