LCA via Binary Lifting, in depth: the jump table, k-th ancestors, ancestor binary search, growing trees and when a sparse table wins

The doubling identity

Let up[0][v] be the parent of v, with the root as its own parent. The doubling identity says that going 2^k levels up is the same as going 2^(k-1) levels up twice:

up[k][v] = up[k-1][ up[k-1][v] ]

So row k of the table is row k-1 composed with itself, and the whole table is built row by row in O(n log n). Making the root its own parent is a deliberate sentinel: any jump that would overshoot the root lands on the root instead of on an invalid index, which keeps the query loops free of bounds checks. The price is that the table can no longer tell you that a jump overshot; the depth array must do that, and every routine below consults it.

Any non-negative k has a binary expansion, so a jump of k levels is a composition of the jumps for its set bits, applied in any order. A jump of 13 = 8 + 4 + 1 is three lookups.

Sizing LOG and laying out the table

The table needs enough rows to express the deepest possible jump. In a path of n nodes the deepest node sits at depth n - 1, so we need 2^LOG > n - 1. The safe choice in Python is LOG = max(1, n.bit_length()), and in C++ LOG = 32 - __builtin_clz(n) for n >= 1. A table one row short works on random trees, which are shallow, and fails on a path, which every serious test set includes.

Memory is n times LOG integers. For a million nodes LOG is 20, so 20 million entries, 80 MB as 32-bit integers: affordable on a server, a problem in a memory-capped judge or embedded service. Use 32-bit node ids.

Prefer row-major up[k][v]: the build loop for row k streams linearly through row k-1 and vectorises well. Node-major up[v][k] keeps one node's ancestors in one cache line, but each query step moves to a different node anyway, so queries gain little from it.

Building without recursion

Recursive DFS is the textbook way to compute parents and depths, and it overflows the call stack on a path of a few hundred thousand nodes in most languages. A breadth-first traversal computes the same two arrays iteratively, and because BFS visits parents before children, the parent row is complete before the doubling rows are built. Here is a full implementation, tested against brute force on random trees of up to 300 nodes:

from collections import deque

class BinaryLifting:
    def __init__(self, n, adj, root=0):
        self.LOG = max(1, n.bit_length())
        self.depth = [0] * n
        up0 = [root] * n                  # root is its own parent
        seen = [False] * n
        seen[root] = True
        q = deque([root])
        while q:                          # iterative BFS: no recursion limit
            u = q.popleft()
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    up0[v] = u
                    self.depth[v] = self.depth[u] + 1
                    q.append(v)
        self.up = [up0]
        for k in range(1, self.LOG):      # row k = row k-1 composed with itself
            prev = self.up[k - 1]
            self.up.append([prev[prev[v]] for v in range(n)])

Two details make this robust. The adjacency list is undirected, so the seen array, not a parent comparison, prevents walking back up; a parent check breaks on multigraph input with duplicate edges. And the build never reads a row that is not finished, because each row depends only on the one before it. For iterative DFS orders that also produce entry and exit times, see iterative DFS with explicit stack frames.

The k-th ancestor: reading k in binary

The k-th ancestor query walks the bits of k from least to most significant and jumps for each set bit. Because jumps commute, the order does not matter, and going low to high avoids computing the top bit. The guard on depth is what the root sentinel makes necessary:

def kth_ancestor(self, v, k):
    if k > self.depth[v]:
        return -1                         # would overshoot the root
    j = 0
    while k:
        if k & 1:
            v = self.up[j][v]
        k >>= 1
        j += 1
    return v

Without the guard, the sentinel silently returns the root for k larger than the depth, and a caller that asked for the ancestor 50 levels up of a depth-3 node gets a plausible but wrong answer. Return a distinct value, or raise, and make callers handle it.

LCA by equalising depth, then lifting

The LCA routine in this article first lifts the deeper node to the depth of the shallower one, using the k-th ancestor query. If they now coincide, that node is the answer. Otherwise both nodes are at equal depth below their LCA, and we lift them together, taking each jump from the largest down only when it keeps them apart:

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

The invariant of the second loop is that u and v are distinct nodes at the same depth, both strictly below the LCA. A jump that makes them equal would land on the LCA or above it, so we refuse it; a jump that keeps them distinct keeps them below it. Greedy from the top bit down, this lands them on the two children of the LCA, and one more parent step finishes. The variant on the LCA article skips depth equalisation by testing ancestry with entry and exit times; it needs two extra arrays and one DFS but does a single lifting loop. Both are O(log n); pick the depth version when you already need depths, and the timer version when you already have an Euler tour.

Worked example: a 12-node tree traced

Take the 12-node tree above. n = 12, so LOG = 4. Running the build produces these rows (index is the node id):

Depths are 0 1 1 2 2 2 3 3 4 4 5 5. Now trace lca(10, 7). Node 10 has depth 5 and node 7 depth 3, so lift 10 by 2 = binary 10: one jump with row 1 takes 10 to up[1][10] = 6. Node 6 is not 7, so lift both from the top. Row 3 gives 0 and 0, equal, refuse. Row 2 gives 0 and 0, refuse. Row 1 gives 1 and 1, refuse. Row 0 gives 3 and 3, refuse. Every jump was refused, so u = 6 and v = 7 are already children of the LCA, and the answer is up[0][6] = 3. The program agrees, and also returns lca(11, 4) = 1, lca(8, 5) = 0 and lca(10, 8) = 6.

For k-th ancestors: kth_ancestor(11, 3) applies rows 0 and 1, 11 to 9 to 3, and returns 3. kth_ancestor(11, 5) returns the root 0, and kth_ancestor(11, 6) returns -1 because 6 exceeds the depth. Those are the measured outputs of the code above, not hand values.

Binary search on the ancestor chain

The same greedy descent answers a more general question: given a predicate that is true at v and stays true for a while as you walk up, then becomes false and stays false, which is the highest ancestor where it still holds? Examples: the oldest version in a version tree still compatible with a client, or the outermost scope that still defines a symbol.

def highest_ancestor_where(self, v, ok):
    # ok must be monotone on the path from v to the root:
    # True on v and on a prefix upward, False afterwards.
    for k in range(self.LOG - 1, -1, -1):
        a = self.up[k][v]
        if self.depth[v] >= (1 << k) and ok(a):
            v = a
    return v

It is binary search over the ancestor chain: O(log n) predicate calls instead of a walk of up to n steps. The depth check stops a jump from clamping to the root and testing the root by accident. For an aggregate over the jumped segment, such as a minimum edge weight, keep a second table with the aggregate per jump, as the LCA article shows.

Growing trees online

Because row k of a node depends only on rows below k of its ancestors, a new leaf can be attached at any time in O(log n), with no rebuild: ideal for trees that only grow, such as version trees or search trees explored online.

class GrowingTree:
    def __init__(self, max_n):
        self.LOG = max(1, max_n.bit_length())
        self.up = [[0] for _ in range(self.LOG)]   # node 0 is the root
        self.depth = [0]

    def add_leaf(self, parent):
        v = len(self.depth)
        self.depth.append(self.depth[parent] + 1)
        self.up[0].append(parent)
        for k in range(1, self.LOG):
            self.up[k].append(self.up[k - 1][self.up[k - 1][v]])
        return v

LOG must be sized for the final node count, not the current one, or late additions run out of rows. In testing, a tree grown leaf by leaf produced exactly the same table as the batch build. Deleting nodes or moving subtrees is not supported: the cached ancestors of every descendant would change. For fully dynamic forests use link-cut trees or Euler tour trees instead.

Failure modes

• LOG one row short. Passes random tests, fails on a path or a caterpillar. Always derive LOG from n with bit_length, and include a path in your tests.
• Recursion depth. A recursive DFS build crashes on deep trees; Python's default limit is 1,000 frames, and raising it trades the exception for a native stack overflow. Build with BFS.
• Sentinel confusion. Using -1 for the root's parent requires a bounds check before every lookup and indexing with -1 in Python silently reads the last node. Use the root as its own parent and check depth instead.
• Forest input. A disconnected graph leaves unreached nodes with depth 0 and parent root, and LCA across components returns a wrong answer instead of an error. Add a virtual super-root, or store a component id and reject cross-component queries.
• Memory blow-up. n log n entries as Python lists of ints cost far more than 4 bytes each. For large n use array('i') or NumPy rows, which also lets the doubling step run as one vectorised gather: up[k] = up[k-1][up[k-1]].

Trade-offs

The Euler tour reduction answers LCA in constant time with a sparse table, and heavy-light decomposition does it in O(log n) with linear memory plus path updates. Binary lifting uniquely gives k-th ancestors, monotone ancestor search and O(log n) leaf insertion. For LCA alone at millions of queries per second on a fixed tree, use the sparse table.

What to do next

1. Implement the BinaryLifting class above, then test it against a brute-force parent walk on random trees and on a path of 100,000 nodes; the path catches both a short LOG and any leftover recursion.
2. Add kth_ancestor with an explicit overshoot result and make every caller handle it.
3. Reproduce the worked example: build the 12-node tree, print the four rows, and confirm lca(10, 7) = 3 and kth_ancestor(11, 6) = -1.
4. Find one monotone predicate in your own domain (version compatibility, scope lookup, threshold on a decreasing weight) and replace a linear ancestor walk with highest_ancestor_where.
5. Measure memory at your real n; if n log n integers do not fit, move to NumPy rows or switch to the Euler tour with a segment tree.
6. Read the companion LCA article for path aggregates and rerooting, then the Euler tour article to see the O(1) query alternative.