LCA and binary lifting on trees

Two nodes in a tree share a common ancestor: their lowest common ancestor (LCA) is the deepest node that lies on the path between them. Finding the LCA is useful for computing distances, comparing node relationships, and solving path queries on trees.

A naive approach walks both nodes up to the root until you find their common ancestor. On a deep tree, this is slow. Binary lifting uses preprocessing to answer LCA queries logarithmically.

The idea: precomputed jumps

Store ancestors at increasing distances: each node remembers its parent, its grandparent (parent of parent), its 4th ancestor, its 8th ancestor, and so on. These are ancestors at distances 1, 2, 4, 8, 16, ... which are powers of two.

When you want to find the LCA of two nodes, first make sure they are at the same depth. If not, jump the deeper node up to match the shallower one. Then jump both nodes up together in decreasing order of jump sizes until they meet.

Preprocessing: building the sparse table

The table has rows for nodes and columns for jump sizes (log scale). ancestors[u][k] stores the 2^k-th ancestor of node u.

Base case: ancestors[u][0] is the parent of u.

Recurrence: ancestors[u][k] is the 2^(k-1)-th ancestor of ancestors[u][k-1]. In code, ancestors[u][k] = ancestors[ancestors[u][k-1]][k-1].

1import math2import sys3
4
5def main() -> None:6    data = sys.stdin.read().split()7    n = int(data[0])8
9    # Build adjacency list10    adj = [[] for _ in range(n)]11    for i in range(1, n):12        u = int(data[2 * (i - 1) + 1])13        v = int(data[2 * (i - 1) + 2])14        adj[u].append(v)15        adj[v].append(u)16
17    # DFS to compute depth18    depth = [-1] * n19    parent = [-1] * n20
21    def dfs(u, p, d):22        depth[u] = d23        parent[u] = p24        for v in adj[u]:25            if v != p:26                dfs(v, u, d + 1)27
28    dfs(0, -1, 0)29
30    # Build sparse table31    LOG = math.ceil(math.log2(n)) + 132    ancestors = [[-1] * LOG for _ in range(n)]33
34    for u in range(n):35        ancestors[u][0] = parent[u]36
37    for k in range(1, LOG):38        for u in range(n):39            if ancestors[u][k - 1] != -1:40                ancestors[u][k] = ancestors[ancestors[u][k - 1]][k - 1]41
42    # Output sparse table43    output = []44    for u in range(n):45        row = [str(ancestors[u][k]) for k in range(LOG)]46        output.append(" ".join(row))47
48    sys.stdout.write("\n".join(output) + "\n")49
50if __name__ == "__main__":51    main()

5
0 1
0 2
2 3
2 4

-1 -1 -1 -1
0 -1 -1 -1
0 -1 -1 -1
2 0 -1 -1
2 0 -1 -1

The table uses O(N log N) space, where N is the number of nodes. Building it takes O(N log N) time.

Querying: finding the LCA

To find the LCA of u and v:

1. If depth[u] < depth[v], swap them. Now u is deeper.
2. Bring u up to match v's depth by jumping in decreasing powers of 2.
3. If u == v, return u. Otherwise, lift both nodes up simultaneously until their parents are the same.

1import math2import sys3
4
5def main() -> None:6    data = sys.stdin.read().split()7    idx = 08    n = int(data[idx])9    idx += 110
11    # Build tree12    adj = [[] for _ in range(n)]13    for _ in range(n - 1):14        u = int(data[idx])15        v = int(data[idx + 1])16        idx += 217        adj[u].append(v)18        adj[v].append(u)19
20    depth = [-1] * n21    parent = [-1] * n22
23    def dfs(u, p, d):24        depth[u] = d25        parent[u] = p26        for v in adj[u]:27            if v != p:28                dfs(v, u, d + 1)29
30    dfs(0, -1, 0)31
32    LOG = math.ceil(math.log2(n)) + 133    ancestors = [[-1] * LOG for _ in range(n)]34
35    for u in range(n):36        ancestors[u][0] = parent[u]37
38    for k in range(1, LOG):39        for u in range(n):40            if ancestors[u][k - 1] != -1:41                ancestors[u][k] = ancestors[ancestors[u][k - 1]][k - 1]42
43    def lca(u, v):44        if depth[u] < depth[v]:45            u, v = v, u46        diff = depth[u] - depth[v]47        for k in range(LOG):48            if (diff >> k) & 1:49                u = ancestors[u][k]50        if u == v:51            return u52        for k in range(LOG - 1, -1, -1):53            if ancestors[u][k] != ancestors[v][k]:54                u = ancestors[u][k]55                v = ancestors[v][k]56        return ancestors[u][0]57
58    q = int(data[idx])59    idx += 160    output = []61    for _ in range(q):62        a = int(data[idx])63        b = int(data[idx + 1])64        idx += 265        output.append(str(lca(a, b)))66
67    sys.stdout.write("\n".join(output) + "\n")68
69if __name__ == "__main__":70    main()

5
0 1
0 2
2 3
2 4
3
3 4
1 4
0 4

2
0
0

Each query takes O(log N) time because you make at most log N jumps.

A worked example

Consider a tree with 5 nodes and edges: 0–1, 0–2, 2–3, 2–4.

1    02   / \3  1   24     / \5    3   4

The sparse table:

1ancestors[u][k]  k=0  k=1  k=2  k=32u=0               -1   -1   -1   -13u=1                0   -1   -1   -14u=2                0   -1   -1   -15u=3                2    0   -1   -16u=4                2    0   -1   -1

(Where -1 means no ancestor exists.)

To find LCA(3, 4): both are at depth 2. Lift node 3 with k=0 to jump 1 level: it goes to node 2. Lift node 4 with k=0 to jump 1 level: it goes to node 2. They are the same, so LCA = 2.

To find LCA(1, 4): node 1 is at depth 1, node 4 at depth 2. Lift node 4 to depth 1 with k=0: it goes to node 2. Now both are at depth 1. Check if they are equal: no. Lift both with k=0: node 1 goes to node 0, node 2 goes to node 0. Their parents are the same, so LCA = 0.

Common mistakes

Mistake 1: Forgetting to swap. If you do not ensure the deeper node is u before lifting, you will lift the wrong node. Always check depth[u] and swap if needed.

Mistake 2: Off-by-one in the depth difference. If depth[u] = 3 and depth[v] = 1, the difference is 2. You need to lift u by 2 levels. Use diff = depth[u] - depth[v] and then jump by powers of 2 within that budget. If (diff >> k) & 1 is true, you jump by 2^k levels.

Mistake 3: Forgetting to check if u == v after equalizing depth. If the two nodes are the same after bringing them to the same depth, return immediately. Do not lift further.

Mistake 4: Indexing ancestors wrongly. Remember that ancestors[u][k] is the 2^k-th ancestor. To jump 1 level, use k=0. To jump 2 levels, use k=1. Be careful with the power-of-two relationship.

A second worked example

Consider a deeper tree with 7 nodes:

1       02      / \3     1   24    / \   \5   3   4   56        \7         6

Edges: 0-1, 0-2, 1-3, 1-4, 2-5, 4-6. Depths: [0, 1, 1, 2, 2, 2, 3].

To find LCA(3, 6): node 3 is at depth 2, node 6 is at depth 3. Lift node 6 by 1 level (k=0): node 6 goes to node 4. Now both are at depth 2. Are they equal? No. Lift both by powers of 2, starting from the highest k. With k=1, we would jump 2 levels, but we are already at depth 2 and need to stay at depth ≥ 1, so we check if ancestors[3][1] and ancestors[4][1] are different. Node 3's 2nd ancestor is node 0 (through 1). Node 4's 2nd ancestor is node 0 (through 1). They are the same, so we do not jump. The LCA is ancestors[3][0] = 1.

Extending binary lifting

The same approach works with arbitrary edge weights. Instead of just tracking ancestors, also track the minimum weight (or maximum, or sum) along the path to each ancestor.

On a tree with node labels, store the label at each ancestor. This allows computing properties of paths: "What is the maximum label on the path from u to v?"

You can also use binary lifting on DAGs (directed acyclic graphs) if you precompute the ancestors in topological order.

Recap

Binary lifting preprocesses the tree to support O(log N) LCA queries and path queries. Build a sparse table of 2^k-th ancestors for each node, then answer queries by jumping in powers of two. Ensure depths are equal before querying, and use bitwise operations to extract the binary representation of jump distances. This technique extends to weighted paths, node labels, and DAG problems.