Lowest Common Ancestor with Binary Lifting in Python
The Nearest Shared Ancestor
In a family tree, the lowest common ancestor of two cousins is their shared grandparent. In a company chart, it is the most junior manager who oversees both employees. In a file system, it is the deepest folder containing both files. In a tree data structure, the lowest common ancestor (LCA) of two nodes is the deepest node that is an ancestor of both. LCA queries are used to find distances between nodes in trees, in version-control systems like Git (finding the merge base of two branches), in phylogenetic trees in biology, and in many competitive programming problems. This tutorial covers the simple "climb up" method, the efficient binary lifting method that answers each query in O(log n), and how to use LCA to compute distances, with Python code whose outputs were checked by running it.
Setting Up a Rooted Tree
We use a tree of 13 nodes rooted at node 0, stored as an adjacency list. A breadth-first search from the root records each node's parent and depth (its distance from the root):
from collections import deque
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (4, 7), (4, 8),
(6, 9), (8, 10), (8, 11), (9, 12)]
n = 13
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
def bfs_parents(root):
parent = [-1] * n
depth = [0] * n
seen = [False] * n
seen[root] = True
q = deque([root])
while q:
u = q.popleft()
for v in adj[u]:
if not seen[v]:
seen[v] = True
parent[v] = u
depth[v] = depth[u] + 1
q.append(v)
return parent, depth
parent, depth = bfs_parents(0)
print("parent:", parent)
print("depth: ", depth)
Output:
parent: [-1, 0, 0, 1, 1, 2, 2, 4, 4, 6, 8, 8, 9] depth: [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4]
Using BFS rather than recursive DFS avoids hitting Python's recursion limit on deep trees.
The Simple Method: Climb Up
To find the LCA of u and v: first lift the deeper node until both are at the same depth, then lift both together, one step at a time, until they are the same node.
def lca_naive(u, v):
while depth[u] > depth[v]:
u = parent[u]
while depth[v] > depth[u]:
v = parent[v]
while u != v:
u, v = parent[u], parent[v]
return u
print(lca_naive(10, 7), lca_naive(10, 3), lca_naive(12, 5), lca_naive(11, 11), lca_naive(7, 12))
Output:
4 1 2 11 0
This is correct, but each query can take O(h) steps, where h is the height of the tree. For a long, thin tree with 100,000 nodes and 100,000 queries, that is up to 10¹⁰ steps, far too slow.
Lowest Common Ancestor with Binary Lifting
Binary lifting speeds up the climbing by precomputing jumps of length 1, 2, 4, 8, … for every node. Let up[k][v] be the ancestor of v that is 2ᵏ levels above it (or −1 if there is none). Then:
up[0][v]is just the parent of v.- A jump of 2ᵏ is two jumps of 2ᵏ⁻¹: up[k][v] = up[k − 1][ up[k − 1][v] ].
The table has about log₂ n rows, so building it takes O(n log n) time and memory.
Any distance can be written in binary as a sum of powers of two, so lifting a node by d levels takes at most log₂ d jumps. For example, lifting by 13 = 8 + 4 + 1 takes three jumps.
LOG = max(1, (n - 1).bit_length())
up = [parent[:]]
for k in range(1, LOG):
prev = up[k - 1]
up.append([prev[prev[v]] if prev[v] != -1 else -1 for v in range(n)])
def lift(v, d):
k = 0
while d and v != -1:
if d & 1:
v = up[k][v]
d >>= 1
k += 1
return v
def lca(u, v):
if depth[u] < depth[v]:
u, v = v, u
u = lift(u, depth[u] - depth[v]) # bring u up to v's depth
if u == v:
return u
for k in range(LOG - 1, -1, -1): # biggest jumps first
if up[k][u] != up[k][v]:
u, v = up[k][u], up[k][v]
return parent[u]
print("LOG =", LOG)
print("4 levels above 12:", lift(12, 4))
print(lca(10, 7), lca(10, 3), lca(12, 5), lca(11, 11), lca(7, 12))
Output:
LOG = 4 4 levels above 12: 0 4 1 2 11 0
Why the Final Loop Works
After lifting, u and v are at the same depth but different. We want to lift them both as high as possible while they stay different. Going through jump sizes from largest to smallest, we take a jump only if it does not make them equal (if it did, we might have jumped past the LCA to a higher common ancestor). At the end, u and v are the two children of the LCA on the paths, so the answer is their parent. This is like finding a number by binary search on its bits, and it takes O(log n) steps per query.
Distances Between Nodes
The path between two nodes in a tree goes up from u to their LCA and then down to v. So the number of edges between them is
dist(u, v) = depth[u] + depth[v] − 2 × depth[lca(u, v)].
def dist(u, v):
return depth[u] + depth[v] - 2 * depth[lca(u, v)]
for a, b in [(10, 7), (12, 3), (5, 6), (11, 12)]:
print(f"dist({a}, {b}) = {dist(a, b)}")
Output:
dist(10, 7) = 3 dist(12, 3) = 6 dist(5, 6) = 2 dist(11, 12) = 8
Check dist(10, 7): 10 → 8 → 4 → 7, three edges ✓. With weighted edges, store each node's distance from the root instead of its depth, and use the same formula.
Testing Against the Simple Method
import random random.seed(3) ok = all(lca(a, b) == lca_naive(a, b) for a in range(n) for b in range(n)) pairs = [(random.randrange(n), random.randrange(n)) for _ in range(5)] print(ok, [(a, b, lca(a, b)) for a, b in pairs])
Output:
True [(3, 9, 0), (8, 2, 0), (5, 9, 2), (7, 10, 4), (9, 1, 0)]
All 169 pairs agree with the straightforward method.
Complexity and Alternatives
- Binary lifting: O(n log n) preprocessing, O(log n) per query. Simple, and the same table answers "k-th ancestor" queries and can store path maximums or sums alongside each jump.
- Euler tour + range minimum query: record nodes in DFS order with depths; the LCA of u and v is the shallowest node between their first appearances. With a sparse table this gives O(1) queries after O(n log n) preprocessing.
- Tarjan's offline LCA: answers a batch of queries known in advance in nearly linear time using union–find.
- For a binary search tree, the LCA is simpler: walk down from the root; the first node whose value lies between u and v is the LCA.
Summary
- The lowest common ancestor of u and v is the deepest node that is an ancestor of both.
- The naive method equalises depths and climbs one step at a time: O(h) per query.
- Binary lifting stores 2ᵏ-th ancestors, up[k][v] = up[k − 1][up[k − 1][v]], and answers queries in O(log n).
- After equalising depths, jump from the largest power down while the ancestors differ; the LCA is then the parent.
- Tree distance: depth[u] + depth[v] − 2 × depth[LCA].