Lowest Common Ancestor, in depth: ancestor tests, path queries, rerooting, virtual trees and merge bases in DAGs

The example tree

An ancestor test in two comparisons

Run one depth-first search and give each node an entry time, tin, from a counter. On leaving a node, record tout, the largest entry time inside its subtree. A subtree's entry times form one contiguous interval, so u is an ancestor of v (counting u as its own ancestor) exactly when tin[u] <= tin[v] <= tout[u].

In the example, node 2 owns the interval [1, 5], so it is an ancestor of 7 (tin 4) and 8 (tin 5) but not of 9 (tin 8). The intervals also turn subtree sums into range sums over an array laid out in entry order.

Binary lifting driven by the ancestor test

Binary lifting stores the 2^k-th ancestor of every node. The usual query lifts the deeper node to equal depth and then lifts both together. With the ancestor test you can lift only one of them: from u, take every jump that does not land on an ancestor of v. Afterwards u sits directly below the answer, so the LCA is its parent. Because jumps past the root saturate at the root, which is an ancestor of everything, the loop never overshoots.

The build is iterative because a recursive DFS exhausts the stack on path-shaped trees long before a million nodes. The table mx is filled alongside up and is explained in the next section.

def build(n, root, adj):
    """adj[u] = [(v, weight), ...] for node ids 0..n-1."""
    LOG = max(1, n.bit_length())             # 2**LOG > any depth
    up = [[root] * n for _ in range(LOG)]    # the root is its own ancestor
    mx = [[0] * n for _ in range(LOG)]       # max edge weight on each jump
    depth, dist, tin, tout = [0] * n, [0] * n, [0] * n, [0] * n
    timer, stack = 0, [(root, -1, 0)]
    while stack:                             # iterative: no recursion limit
        u, par, w = stack.pop()
        if u < 0:                            # exit marker ~u: subtree finished
            tout[~u] = timer - 1
            continue
        tin[u], timer = timer, timer + 1
        if par >= 0:
            up[0][u], mx[0][u] = par, w
            depth[u], dist[u] = depth[par] + 1, dist[par] + w
        stack.append((~u, par, 0))
        for v, wv in reversed(adj[u]):       # reversed: visit children in list order
            if v != par:
                stack.append((v, u, wv))
    for k in range(1, LOG):
        for v in range(n):
            mid = up[k - 1][v]
            up[k][v] = up[k - 1][mid]
            mx[k][v] = max(mx[k - 1][v], mx[k - 1][mid])
    return LOG, up, mx, depth, dist, tin, tout


LOG, up, mx, depth, dist, tin, tout = build(n, root, adj)   # globals used below


def is_anc(u, v):
    return tin[u] <= tin[v] <= tout[u]


def lca(u, v):
    if is_anc(u, v):
        return u
    if is_anc(v, u):
        return v
    for k in range(LOG - 1, -1, -1):
        if not is_anc(up[k][u], v):          # jump while still below the answer
            u = up[k][u]
    return up[0][u]

Trace LCA(4, 8): neither interval contains the other. Every jump from 4 lands on an ancestor of 8 (the root for jumps of 8, 4 and 2, and node 2, owning [1, 5], for a jump of 1), so 4 never moves and the answer is its parent, 2.

Distances and path aggregates

The path from u to v climbs to their LCA a and descends, so any path quantity splits into two root-ward pieces. The technique depends on whether the operation can be undone.

If it can, as with sums and XOR, precompute the value from the root to every node and subtract. The weighted distance is dist[u] + dist[v] - 2 * dist[a], and an edge count is the same formula with depths. If it cannot, as with maximum, minimum or gcd, store the aggregate next to each jump: mx[k][v] is the largest weight on the 2^k edges above v, built from two half-jumps. A query climbs from each endpoint to the LCA, combining as it goes.

def climb_max(u, anc):
    """Largest edge weight on the path from u up to its ancestor anc."""
    best = 0
    for k in range(LOG - 1, -1, -1):
        if depth[u] - (1 << k) >= depth[anc]:
            best = max(best, mx[k][u])
            u = up[k][u]
    return best


def distance(u, v):
    return dist[u] + dist[v] - 2 * dist[lca(u, v)]


def path_max(u, v):
    a = lca(u, v)
    return max(climb_max(u, a), climb_max(v, a))

Path maximum is not a contest trick: the largest edge on a minimum spanning tree path is the edge a new link must beat to change the tree, which is how you find the second-best spanning tree or test whether a new link improves a network. For how the spanning tree itself is built, see Prim's algorithm.

Worked example: distances and bottlenecks

Root distances in the example are 4 for node 2, 5 for 5, 8 for 7, 11 for 8 and 15 for 10.

For path_max(4, 8), climbing from 8 to 2 needs two edges. A jump of 2 from 8 reaches 2 with the stored maximum of edges 6 and 1, which is 6; climbing from 4 is one jump of 1 with weight 7. The answer is 7. Compare against a brute-force parent walk on random trees before trusting the table.

Changing the root without rebuilding

Some problems ask for LCAs under a root that changes per query. Rebuilding costs O(n log n) per root, and is unnecessary. Keep the tables for one fixed root, and for root r the answer is the deepest, by the fixed depths, of three ordinary queries: lca(u, v), lca(u, r) and lca(v, r).

The answer under root r is where the paths from u and v toward r first join, and in the fixed rooting that junction is the deepest of the three pairwise LCAs; the other two coincide higher up. Check it on the example with r = 7, u = 8 and v = 4. The three queries give 2, 5 and 2, and the deepest is 5. Walking by hand under root 7, node 8 reaches the root through 5, node 4 through 2 and 5, so they first share 5. With r = 9, u = 10 and v = 4, the queries give 1, 6 and 1, so the answer is 6, which is where the path from 4 joins the path from 10 on its way to 9.

Virtual trees for many small queries

A common workload is many queries that each touch k nodes of a large tree: the cost of connecting k offices over a fixed backbone, or the dependency subgraph behind k changed files. A tree DP over all n nodes per query is too slow when queries number in the thousands. A virtual tree keeps only the marked nodes and the LCAs where their paths branch; each edge stands for a compressed path.

The branching points are exactly the LCAs of nodes adjacent in entry-time order, so k marked nodes need at most k - 1 extra nodes. Sort by tin, add those LCAs, sort again, and connect each node to the nearest ancestor on a stack. The cost is O(k log k) for sorting plus O(k log n) for the LCA queries, independent of n.

def virtual_tree(marked):
    vs = sorted(set(marked), key=tin.__getitem__)
    joins = [lca(a, b) for a, b in zip(vs, vs[1:])]
    vs = sorted(set(vs) | set(joins), key=tin.__getitem__)
    edges, stack = [], [vs[0]]               # vs[0] is the LCA of all of them
    for v in vs[1:]:
        while not is_anc(stack[-1], v):
            stack.pop()
        edges.append((stack[-1], v, dist[v] - dist[stack[-1]]))
        stack.append(v)
    return vs[0], edges

For the marked set {7, 8, 10}, the adjacent LCAs are 5 and 1. The stack produces edges 1-5 (weight 5), 5-7 (3), 5-8 (6) and, after popping 8 and 5, 1-10 (15). The weights total 29, exactly the weight of the smallest subtree connecting 7, 8 and 10 (3 + 6 + 1 + 4 + 2 + 5 + 8). Equivalently, the distances between consecutive marked nodes in entry order, round the cycle (9 + 26 + 23 = 58), sum to twice that weight.

When ancestors form a DAG: merge bases

In version control, merge commits have several parents, so history is a DAG, and a three-way merge needs a merge base: a common ancestor that no other common ancestor descends from. A tree has exactly one; a DAG can have several, and the tree methods above, which assume one parent, do not apply.

The definition translates directly into a correct, if unoptimised, algorithm: intersect the two ancestor sets, then drop every common ancestor that is reachable from another one.

def merge_bases(a, b, parents):
    def ancestors(starts):
        seen, todo = set(starts), list(starts)
        while todo:
            for q in parents[todo.pop()]:
                if q not in seen:
                    seen.add(q)
                    todo.append(q)
        return seen
    common = ancestors([a]) & ancestors([b])
    # drop common ancestors that are strict ancestors of another one
    redundant = ancestors([q for c in common for q in parents[c]])
    return common - redundant

The case that produces several answers is the criss-cross merge. Two branches start from R with commits X and Y. Branch one merges Y into X, branch two merges X into Y, and each continues with a commit, A and B. The common ancestors of A and B are X, Y and R; R is an ancestor of both X and Y and is dropped, which leaves two merge bases, X and Y, neither better than the other. Git reports one by default and all of them with git merge-base --all A B. Its merge strategies handle the ambiguity by merging the merge bases first into a virtual common ancestor, which is why criss-cross histories can produce conflicts that look unrelated to either branch.

Production implementations walk both histories at once from a priority queue ordered by generation number (always larger for a child than for its parents), mark each commit with the sides that reached it, and stop once everything queued lies below a common ancestor; Git keeps generation numbers in its commit-graph file for this. Whenever your data has merges, decide whether you need one answer or the set.

Failure modes

• Wrong or missing root. An undirected edge list has no root until you choose one. Every answer depends on it, and rerooting quietly is a bug, not a feature. Store the root with the tables.
• Recursion on deep trees. Recursive DFS fails on path-shaped inputs. Use an explicit stack, as above, and test with a 10^6-node chain.
• Off-by-one in LOG. If 2^LOG does not exceed the maximum depth, the jump loop cannot reach the answer on deep trees and returns a wrong node, with no exception.
• Forest input. Nodes outside the root's component keep default values and give silently wrong answers. Check that the DFS visited all n nodes.
• Subtracting a non-invertible aggregate. Root-prefix subtraction is right for sums and wrong for maximum. Use jump aggregates for anything you cannot undo.
• Mutation without rebuild. Appending a leaf is cheap with lifting; re-parenting a subtree invalidates entry intervals, so batch changes and rebuild.

Trade-offs

Memory usually binds first. For a million nodes, 20 levels of up and mx as 32-bit integers take about 160 MB, so use typed arrays, and drop mx if you only need distances. For the range-minimum route to LCA and its link to Cartesian trees, see Cartesian trees and range minimum; for stack-based traversal patterns, iterative DFS with an explicit stack; and for the offline approach built on union-find, the LCA deep dive linked above.

What to do next

1. Implement build, is_anc and lca and test them against a brute force on random trees, including chains and stars.
2. Verify distance(u, v) against breadth-first search on small weighted trees.
3. Add path-maximum aggregates, check them against a path walk, and use them on MST paths.
4. Check three-query rerooting by rebuilding the tables for a few random roots.
5. Assert that virtual-tree edge weights equal half the cyclic entry-order distance total.
6. If your data has merges, use a merge-base routine that returns a set, tested on a criss-cross case.