Binary Lifting: Fast Ancestor and LCA Queries on Trees

"Find the k-th ancestor of a node" or "find the lowest common ancestor of u and v" is easy once per query by walking up parent pointers. With many queries on a deep tree, that's O(n) each. Binary lifting makes every query O(log n).

The jump table

up[j][v] is the 2^j-th ancestor of v. Row 0 is the parent array, and each row doubles the previous: up[j][v] = up[j-1][ up[j-1][v] ].

LOG = 17  # enough for n up to ~131k

def build(parent, n):
    up = [parent[:]]
    for j in range(1, LOG):
        prev = up[-1]
        up.append([prev[prev[v]] if prev[v] != -1 else -1 for v in range(n)])
    return up

def kth_ancestor(up, v, k):
    j = 0
    while k and v != -1:
        if k & 1:
            v = up[j][v]
        k >>= 1; j += 1
    return v

LCA in O(log n)

1. Lift the deeper node until both nodes are at the same depth (a k-th ancestor query with k = depth difference).
2. If they're now equal, that's the LCA.
3. Otherwise, for j from high to low, if up[j][u] != up[j][v], jump both. They end just below the LCA, so return the parent.

def lca(up, depth, u, v):
    if depth[u] < depth[v]: u, v = v, u
    u = kth_ancestor(up, u, depth[u] - depth[v])
    if u == v: return u
    for j in reversed(range(LOG)):
        if up[j][u] != up[j][v]:
            u, v = up[j][u], up[j][v]
    return up[0][u]

Complexity

O(n log n) preprocessing time and memory, O(log n) per query. Compare with an Euler tour plus sparse table (O(1) LCA queries, more code) and Tarjan's offline LCA (near-linear, but needs all queries up front).

Beyond ancestors

• Store an aggregate alongside each jump, such as the max edge weight on the 2^j path, to answer path-max queries.
• The same doubling idea works on any functional graph: "where am I after k steps?" in permutation or successor-graph problems.

Interview framing: "I'll precompute 2^j ancestors so any jump decomposes into powers of two; LCA equalises depths, then lifts both nodes greedily."

Disclosure: written by the team at linkjob.ai (AI interview assistant). Use freely for practice.