Following a parent pointer once is cheap. Following it thousands of times for every query repeats the same work. If we store where a vertex lands after 1, 2, 4, 8 and further powers of two parent steps, we can assemble a long upward journey from its binary digits.
This is binary lifting, or ancestor doubling. The doubling principle resembles binary exponentiation, but the objects being composed are parent maps rather than numbers. We will first prove what each table entry means, then use the table to find a lowest common ancestor. The latter algorithm needs its own invariant: knowing how to jump quickly does not tell us which jumps are safe.
The tree and chosen root remain fixed after preprocessing. This method supplies static ancestor and distance queries; it does not replace heavy-light decomposition for maintaining general values along changing paths.
Rooted trees distinguish depth from a table convention
Input is a nonempty undirected tree on vertices , with a selected root . A tree is connected and has no cycle, so there is one simple path between each pair of vertices. The depth is the number of edges on the root-to- path. A nonroot vertex's parent is the preceding vertex on that path.
Definition 13.2.1
(Real ancestors and a root-clamped parent map)
The kth ancestor of , for integer , is the vertex reached by taking exactly parent steps toward the root. It exists if and only if . The zeroth ancestor is itself. Beyond the root there is no real ancestor.
For table construction only, define a total map : use the real parent away from the root, and set . Store
Here the exponent counts repeated function composition. The map stays at the root if a table jump goes too far. That padding makes every lookup valid; it does not change the existence rule for a real kth ancestor.
Definition 13.2.2
(Lowest common ancestor)
The real ancestors of a vertex are precisely the vertices on its root path, including itself. For two vertices, the intersection of their root paths is a common initial path. Its deepest vertex is therefore a unique lowest common ancestor, abbreviated LCA. “Lowest” means greatest depth, not smallest vertex label.
Compose powers of one parent operation
Theorem 13.2.3
(Kth ancestor by binary composition)
For every vertex and every integer , write with . Replacing the current vertex, starting from , by its row- entry for every with gives the kth ancestor of , and every such is a stored row, where the number of rows is the bit length of , at least .
Proof
(Doubling and binary digits)
The base row applies once. If row applies it times, applying that row twice applies it times, proving the next row by induction.
Write a valid request as with . For each set bit, replace the current vertex by its row- ancestor. Since these are powers of the same map, their composition applies exactly times. Every partial sum of chosen steps is at most , so the process never needs the artificial part above the root.
For a tree of vertices, depth is at most . Thus rows, indexed 0 through , represent every valid distance. The one-vertex case retains one base row. Check a request's depth bound before trying to read its bits from the table.
Proof X-ray
Why the padded part of the table is never touched
The proof needs one thing from : every partial sum of the chosen powers is at most , so every intermediate vertex is a real ancestor and the padding rule is never invoked. The order of the jumps is irrelevant, because composing powers of one map is associative and commutes with itself. The row count is a separate, purely arithmetic fact: bounds the highest set bit of .
Counterexample mode
Root padding is not a promise of infinitely many ancestors
For a vertex at depth 2, a request for its third ancestor has no answer. A table whose root points to itself would still return the root if used without a depth check. That result describes the padded map, not three real parent steps.
The code will return None for and reject a negative . In particular, the root's zeroth ancestor is the root, while its first ancestor does not exist. A huge invalid must be rejected by the depth bound before it could request a nonexistent table row.
A jump table for a branching tree
Worked example 13.2.4
(Assemble a five-step climb from one-step and four-step jumps)
Use eight vertices, root 0, and edges , , , , , , . The two branches split at vertex 2. Three table rows are sufficient because has three binary digits.
| Vertex | Depth | : one step | : two steps | : four steps |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 2 | 2 | 1 | 0 | 0 |
| 3 | 3 | 2 | 1 | 0 |
| 4 | 4 | 3 | 2 | 0 |
| 5 | 5 | 4 | 3 | 1 |
| 6 | 3 | 2 | 1 | 0 |
| 7 | 4 | 6 | 2 | 0 |
To take five steps from vertex 5, use : jump first to , then to . Equivalently, four steps first reach 1 and one more reaches 0. Both orders compose the same five parent steps. A sixth-ancestor request returns None, even though padded table composition could stay at 0.
Worked example 13.2.5
(A path graph and the full-depth ancestor)
Let the tree be the path rooted at , so and rows hold jumps of . The seventh ancestor of uses : , then , then , which is . The ancestor at the full depth, , gives and then , the root. A request with returns None, although padded composition would also land on .
Equalize depths before comparing two upward paths
To find , first lift the deeper endpoint by the depth difference. The LCA is unchanged: vertices removed below the shallower endpoint's depth cannot be common ancestors. Both current vertices now have the same depth. If they coincide, that vertex is the answer, including the case where one original endpoint was an ancestor of the other.
Otherwise the current vertices are distinct and both lie strictly below their true LCA . Consider the same jump length from each. If their proposed ancestors differ, both jumps stay strictly below and can safely be taken. If the proposed ancestors are equal, the jump reaches or passes ; taking it could skip the answer.
Theorem 13.2.6
(Correctness of the LCA scan)
Lift the deeper of by the depth difference. If the two vertices coincide, that vertex is . Otherwise scan , replacing both vertices by their row- ancestors whenever those ancestors differ. The scan ends at two distinct vertices whose common parent is .
Proof
(Descending unequal jumps)
Equal-depth distinct vertices have the same positive distance to their LCA . Their upward paths remain disjoint until reaching , then coincide. Therefore holds exactly when . Root-clamped lookup preserves equality even for jumps that would go above the root.
When the proposed ancestors differ, replacing both endpoints by them subtracts from and preserves the same LCA. Otherwise leave both endpoints unchanged. Scan levels from down to 0. Initially . If before level we have , then either and no jump is taken, or a jump subtracts and leaves .
By induction, after level 0 we have . The two current vertices are distinct children of , so their common parent is exactly the answer. The algorithm never needs to know while running; inequality of the two proposed table entries certifies every safe move.
Proof X-ray
Why inequality is the right test
The scan uses exactly one fact about the unknown LCA : for two vertices at equal distance below , their row- ancestors differ if and only if . So “differ” certifies a jump that stays strictly below , while “equal” says only that the jump would reach or pass , not how far is. The invariant makes the scan a binary search on : each level either leaves unchanged because , or subtracts and leaves . Scanning upward from level would fail, because a small jump taken early can leave a distance that needs a larger jump already passed.
Counterexample mode
Jumping when ancestors are equal can skip the desired ancestor
Take edges , , , rooted at 0. The LCA of 2 and 3 is 1. Their two-step table ancestors are both 0. Moving both endpoints there merely because these entries agree would pass vertex 1 and lose the answer.
The correct loop moves on unequal proposed ancestors, staying below the LCA. Equal proposals are a reason to try a shorter jump. The equality test after depth equalization is different: if the current vertices themselves coincide, we have already reached the answer and return immediately.
Common mistake
(Scanning the levels upward)
The levels must run from down to . Take two vertices at distance below their LCA. Scanning upward, level differs and moves both up one step, leaving ; level now has equal proposals, so nothing moves; the scan ends two edges below the LCA and returns the wrong vertex, a child of the true LCA. Scanning downward tests the -step jump first, rejects it, takes the -step jump, rejects the -step jump, and stops at distance , whose parent is the LCA.
Derive the unweighted distance
Theorem 13.2.7
(Distance from depths and the LCA)
For vertices of a tree with lowest common ancestor , the number of edges on the unique – path is
Proof
(Climb, then descend)
The path climbs from to along edges and then descends to along edges. The two parts share no edge, because below they lie on different root paths; if or , one part is empty. Adding the two counts gives the formula.
Common mistake
(Depth is not weighted distance)
This formula counts edges. If edges have other lengths or weights, plain depth is not their weighted distance and must not be substituted without changing the stored quantities and proof.
Worked example 13.2.8
(Equalize first, then stop below the branch point)
In the eight-vertex tree, vertex 5 has depth 5 and vertex 7 has depth 4. Lift 5 once to 4, so compare vertices 4 and 7 at depth 4. Four-step proposals both give 0; two-step proposals both give 2. Neither pair is taken.
The one-step proposals are 3 and 6, which differ. Move to those vertices, then return their common parent 2. Thus , and the distance is . The actual path is , containing five edges.
For endpoints 3 and 5, equalizing depths already brings 5 to 3, so the LCA is returned before the simultaneous-jump loop. For equal endpoints, the LCA is that vertex and the distance is zero.
Executable implementation with a tree contract
The constructor accepts positive integer , an undirected edge list of integer endpoint pairs, and an integer root label. It validates endpoints, exactly edge instances and connectivity. Those last two conditions guarantee a tree even if the supplied list attempted self-loops or duplicate edges: a connected graph already needs spanning-tree edges, leaving no extra edge instance for a loop, parallel copy or cycle.
Breadth-first traversal records parents and depths without recursion. Its queue marks vertices upon discovery. Query labels must lie in ; invalid or negative labels are rejected before any table access. The constructor reads but does not mutate the edge list.
from collections import deque
class AncestorTable:
def __init__(self, n, edges, root=0):
if n <= 0 or not 0 <= root < n:
raise ValueError("a nonempty tree and a valid root are required")
graph = [[] for _ in range(n)]
edge_count = 0
for u, v in edges:
if not (0 <= u < n and 0 <= v < n):
raise ValueError("edge endpoint outside the vertex range")
graph[u].append(v)
graph[v].append(u)
edge_count += 1
if edge_count != n - 1:
raise ValueError("a tree must have exactly n - 1 edges")
parent = [-1] * n
depth = [0] * n
parent[root] = root
pending = deque([root])
reached = 1
while pending:
vertex = pending.popleft()
for neighbor in graph[vertex]:
if parent[neighbor] == -1:
parent[neighbor] = vertex
depth[neighbor] = depth[vertex] + 1
reached += 1
pending.append(neighbor)
if reached != n:
raise ValueError("the tree must be connected")
self.n = n
self.depth = depth
self.up = [parent]
levels = max(1, (n - 1).bit_length())
for _ in range(1, levels):
previous = self.up[-1]
self.up.append([previous[previous[v]] for v in range(n)])
def _vertex(self, vertex):
if not 0 <= vertex < self.n:
raise IndexError("vertex outside the tree")
def ancestor(self, vertex, k):
self._vertex(vertex)
if k < 0:
raise ValueError("the ancestor distance must be nonnegative")
if k > self.depth[vertex]:
return None
level = 0
while k:
if k & 1:
vertex = self.up[level][vertex]
k >>= 1
level += 1
return vertex
def lca(self, u, v):
self._vertex(u)
self._vertex(v)
if self.depth[u] < self.depth[v]:
u, v = v, u
u = self.ancestor(u, self.depth[u] - self.depth[v])
if u == v:
return u
for level in range(len(self.up) - 1, -1, -1):
if self.up[level][u] != self.up[level][v]:
u = self.up[level][u]
v = self.up[level][v]
return self.up[0][u]
def distance(self, u, v):
common = self.lca(u, v)
return self.depth[u] + self.depth[v] - 2 * self.depth[common]
The code assumes the promised integer labels, counts and values. A valid equalizing lift cannot return None, since its distance is at most the deeper endpoint's depth. For one vertex, the table is [[0]], ancestor distance zero returns 0, any positive distance returns None, and lca(0,0) returns 0.
Proposition 13.2.9
(Cost of the ancestor table)
For a tree with vertices, preprocessing takes time and space, and every ancestor, LCA or distance query takes time, assuming constant-time indexing, bit operations and integer arithmetic.
Proof
(Counting rows and loop iterations)
Building the graph and rooted parent data takes time for valid input. The table has cells and takes time to fill. Thus preprocessing and storage are , while each ancestor, LCA or distance query takes worst-case time under standard indexing, bit-operation and integer-arithmetic assumptions. The small includes the one-vertex case. These are not arbitrary-integer bit-complexity bounds.
Changing the chosen root changes the ancestor relation and can change LCAs. It does not change the unique undirected path or its edge count. Changing the tree's edges after construction invalidates the preprocessing; dynamic topology needs a separate data structure or a rebuild.
Exercises with complete solutions
Quick check
(1. In the eight-vertex example, find the third, fifth and sixth ancestors of vertex 5. Explain why a padded lookup is insufficient for the last request.)
Solution · 1. Distinguish real steps from root padding
The third ancestor is 2 along ; the fifth is 0. The sixth does not exist because vertex 5 has depth 5, so the function returns None. Composing the padded map six times would stay at 0, but that is not a sixth real ancestor. The depth check enforces the stated query meaning.
Quick check
(2. Derive the four-step table entry from two-step entries. Why can the same table answer a three-step request even though no row stores three steps?)
Solution · 2. Compose stored powers to obtain other distances
and , so . Three steps use : one step reaches 4 and two more reach 2. Rows store powers of two, while binary composition provides every valid sum of those powers.
Quick check
(3. Find LCA(5,7) and their edge distance in the example. Which simultaneous jump is actually taken after equalizing depths?)
Solution · 3. Stay below the common ancestor until the final parent step
First lift 5 to 4. Four-step and two-step proposals agree and are not taken. The one-step proposals are 3 and 6, so both vertices move there; their parent is 2, the LCA. The edge distance is , matching path .
Quick check
(4. In the tree 0-1 with leaves 2 and 3 attached to 1, why is taking the equal two-step proposals from 2 and 3 incorrect? When does equality instead justify returning immediately?)
Solution · 4. Equal proposed jumps differ from equal current vertices
The two-step proposals both reach 0, above the true LCA 1. Taking them loses the nearest common ancestor. The simultaneous loop therefore takes only unequal proposals. After depth equalization, if the current endpoints themselves are equal, that shared vertex is already their LCA and is returned immediately. These are different equality tests with different meanings.
Quick check
(5. On the path 0-1-2, compare LCA(0,2) when the root is 0 and when it is 2. Does the edge distance change?)
Solution · 5. Root-dependent ancestry and root-independent distance
With root 0 the LCA is 0; with root 2 it is 2. Both represent the common initial part of the corresponding rooted paths. The unique undirected path still has two edges, and the depth formula gives 2 under either rooting. Preprocessing must be rebuilt to use the new root's ancestor relation.
Quick check
(6. An input has n=4 and edges (0,1),(1,2),(2,0). It has n−1 edges, so why must the constructor reject it? Why do edge count and connectivity together suffice for an undirected edge-list input?)
Solution · 6. Count alone does not establish a tree
The edges form a triangle on three vertices and leave vertex 3 isolated, so the connectivity check fails. Every connected undirected graph has a spanning tree with edge instances. If the entire input also has exactly that many, all its edges must be those spanning-tree edges, leaving no extra edge for a cycle, loop or parallel copy. Both conditions are necessary for the accepted tree contract.