Offline LCA, in depth: the Tarjan algorithm with union-find, its invariant, a hand trace, an iterative implementation, the representative-label bug and measured cost

When offline beats online

There are two kinds of LCA workload. Online workloads receive queries one at a time and need each answer before the next query arrives; they use binary lifting or an Euler tour with a sparse table, which cost O(n log n) memory and preprocessing. Offline workloads have the whole query list in hand. For them the Tarjan algorithm needs only a few integer arrays of length n plus the queries, makes one pass, and has no log factor in memory.

Offline LCA fits batch jobs: tree distances for every non-tree edge of a graph over a spanning tree, or taxonomic classifiers that combine pairs of taxa into their common ancestor while building a database. If queries arrive over a network, or the tree grows between queries, read Online LCA, in depth instead. For a survey of every method side by side, see Lowest Common Ancestor algorithms.

When offline beats online

There are two kinds of LCA workload. Online workloads receive queries one at a time and need each answer before the next query arrives; they use binary lifting or an Euler tour with a sparse table, which cost O(n log n) memory and preprocessing. Offline workloads have the whole query list in hand. For them the Tarjan algorithm needs only a few integer arrays of length n plus the queries, makes one pass, and has no log factor in memory.

Offline LCA fits batch jobs: tree distances for every non-tree edge of a graph over a spanning tree, or taxonomic classifiers that combine pairs of taxa into their common ancestor while building a database. If queries arrive over a network, or the tree grows between queries, read Online LCA, in depth instead. For a survey of every method side by side, see Lowest Common Ancestor algorithms.

The invariant that makes it work

Run a depth-first search from the root. Call a node finished once its whole subtree has been explored. When a node u finishes, merge its set into the set of its parent p, and label the merged set with p. Because p is still open (on the DFS stack), the label of any set is always the shallowest node of that set that is still on the stack.

Now take the moment node u finishes, and any finished node v. Walk up from v. Every ancestor of v up to, but not including, the first ancestor still on the stack is finished and has been merged upward. The first open ancestor of v is therefore the label of v's set. That open ancestor is also an ancestor of u, because the open nodes are exactly the path from the root to u. No deeper node is an ancestor of both, since every node below it on v's side is finished and not on u's path. So the label of the set containing v is the LCA of u and v. That is the whole proof, and it tells you exactly which data the algorithm needs: a set structure, a label per set, a finished flag per node, and each query stored at both endpoints, because whichever endpoint finishes second answers it.

A hand trace on a nine-node tree

Use the nine-node tree in the diagram: 0 has children 1, 2 and 3; 1 has children 4 and 5; 4 has children 7 and 8; 3 has child 6. The queries are (7, 8), (7, 5), (8, 2), (5, 6), (4, 4) and (3, 6).

1. The DFS goes 0, 1, 4, 7. Node 7 finishes; its only query partners, 8 and 5, are not finished, so nothing is answered. Merge 7 into 4; the label is 4.
2. Node 8 finishes. Its partner 7 is finished, and the label of find(7) is 4, so LCA(7, 8) = 4. Partner 2 is not finished. Merge 8 into 4.
3. Node 4 finishes and answers (4, 4) with label 4, the label of its set {4, 7, 8}. Merge into 1; the set {1, 4, 7, 8} is labelled 1.
4. Node 5 finishes. Partner 7 is finished and the label of its set is 1, so LCA(7, 5) = 1. Partner 6 is not finished. Merge 5 into 1. Node 1 finishes and merges into 0; the label becomes 0.
5. Node 2 finishes. Partner 8 is finished, its set is labelled 0, so LCA(8, 2) = 0. Merge into 0.
6. Node 6 finishes. Partner 5 has label 0, so LCA(5, 6) = 0. Partner 3 is not finished yet. Merge 6 into 3, label 3. Node 3 finishes, sees partner 6 finished with label 3, so LCA(3, 6) = 3.

The program below prints [4, 1, 0, 0, 4, 3] for these queries, matching the trace. Notice that (4, 4) is answered when 4 finishes: a self-query is stored twice at the same node, and both copies see a finished partner. That is harmless, but it is worth a test.

An iterative implementation

A recursive DFS is the textbook form, but Python's default recursion limit is 1,000 and a native thread stack is typically 1 to 8 MB, so a path-shaped tree with a million nodes kills either. The version below uses an explicit stack of (node, next child index) pairs, so a node finishes exactly when its child index runs out. Union-find uses union by rank and a two-pass path compression, both iterative.

def offline_lca(n, children, root, queries):
    """children: list of child lists; queries: list of (u, v). Returns list of LCAs."""
    parent = list(range(n))   # DSU parent
    rank = [0] * n
    anc = list(range(n))      # anc[r] = ancestor label for the set whose root is r
    done = [False] * n
    bucket = [[] for _ in range(n)]
    for qi, (u, v) in enumerate(queries):
        bucket[u].append((v, qi))
        bucket[v].append((u, qi))
    ans = [-1] * len(queries)

    def find(x):
        r = x
        while parent[r] != r:
            r = parent[r]
        while parent[x] != r:          # path compression, second pass
            parent[x], x = r, parent[x]
        return r

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return ra
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1
        return ra

    stack = [(root, 0)]               # (node, index of next child to visit)
    while stack:
        u, i = stack[-1]
        if i < len(children[u]):
            stack[-1] = (u, i + 1)
            stack.append((children[u][i], 0))
            continue
        stack.pop()
        done[u] = True                # u's whole subtree has been visited
        for v, qi in bucket[u]:
            if done[v]:
                ans[qi] = anc[find(v)]
        if stack:
            p = stack[-1][0]
            r = union(p, u)
            anc[r] = p                # label the merged set's root, whichever it is
    return ans

Note the order inside the finish step: mark u finished, answer its queries, then merge it into the parent. Answering before the merge is what lets a self-query or a query to a descendant read u's own label; merged first, the label would already be the parent.

The representative-label bug

The most common bug is one line. Many write-ups store the label on the tree node: after union(p, u) they write anc[p] = p. That is only correct if the union happened to make p's root the root of the merged set. With union by rank, the root of the child's set wins whenever it has the higher rank, which happens as soon as the child's subtree has absorbed one child of its own. The label then sits on a node that find never returns, and later queries read a stale label from deeper in the tree.

The correct rule is to store the label on the representative: anc[find(p)] = p, or, as above, on the root returned by union. On the nine-node example the buggy version prints [4, 4, 4, 4, 4, 3]: once {4, 7, 8} has rank 1, merging it into 1 leaves 4 as the root, every later label write goes to node 1 or 0, and every query reads the stale label 4. Run against brute force on 300 random trees of up to 60 nodes, the buggy version was wrong on 283 of them. Without union by rank the parent's root always survives, which hides the bug until someone adds the heuristic for speed.

def brute(par, depth, u, v):
    while depth[u] > depth[v]: u = par[u]
    while depth[v] > depth[u]: v = par[v]
    while u != v: u, v = par[u], par[v]
    return u

rng = random.Random(7)
for trial in range(300):
    n = rng.randrange(1, 60)
    par = [-1] + [rng.randrange(i) for i in range(1, n)]   # random recursive tree
    children = [[] for _ in range(n)]
    for i in range(1, n): children[par[i]].append(i)
    depth = [0] * n
    for i in range(1, n): depth[i] = depth[par[i]] + 1
    qs = [(rng.randrange(n), rng.randrange(n)) for _ in range(40)]
    assert offline_lca(n, children, 0, qs) == [brute(par, depth, u, v) for u, v in qs]

Keep this harness in your test suite; it covers n = 1, self-queries and ancestor pairs for free. For more on representative choice and why union by rank changes which node is the root, see Union-Find variants.

Edge cases in real query files

• Repeated queries. Each query keeps its own index, so duplicates are answered independently; with heavy repetition, deduplicate first and fan answers back out.
• Self-queries. (u, u) lands in u's bucket twice and is answered when u finishes. Some implementations skip a partner equal to u; if you do, answer self-queries up front.
• Forests. Run the DFS from every root, or add a virtual super-root with every real root as a child. With a super-root, a query whose answer is the super-root means the two nodes are in different trees; report that explicitly rather than returning a fake node id.
• Invalid ids. Validate every endpoint against n before bucketing. A negative id in Python silently indexes from the end of the list and returns a plausible wrong answer.

Measured cost

Each node is pushed and popped once, each query is stored twice and checked twice, and union-find with both heuristics costs O(alpha(n)) amortised per operation, where alpha is the inverse Ackermann function and never exceeds 4 for any practical n. Total time is O((n + q) alpha(n)) and memory is O(n + q). Gabow and Tarjan later showed that the union-find operations on this special structure can be done in strictly linear time, but the extra machinery is rarely worth it in practice.

Measured in pure Python 3.13 on one laptop core, the code above answered a million random queries on a million-node path in 8.7 seconds and on a million-node random recursive tree in 15.1 seconds. The path is likely faster despite its depth because each node has one child and the arrays are touched in order, while in the random tree children and queries point all over memory. A compiled version with flat arrays is far faster; in Python, budget memory for the bucket lists, about two tuples per query.

Distances and path aggregates

Once you have LCAs you have distances: with depths from the same DFS, dist(u, v) = depth[u] + depth[v] - 2 * depth[lca]. For weighted trees use the root distance instead of the depth. Path sums work the same way with prefix sums from the root.

Path minimum or maximum (the bottleneck edge between u and v) needs more: extend the union-find so each node also carries the minimum weight on its path to its set root, updated during path compression, and combine the halves for u and v when the second endpoint finishes. Keep a brute-force path walk in the tests for it too.

For many batches on a static tree, build an Euler tour with a sparse table once; for k-th ancestors as well, use binary lifting.

Choosing an LCA method

Failure modes

• Stack overflow on deep trees. Recursive DFS fails silently in some runtimes (a segfault in C, a crash of the worker in Python with a raised recursion limit). Use an explicit stack and test on a path of the maximum size you accept.
• Label on the wrong node. Write the label to the root returned by union, never to the tree node. The brute-force harness finds it immediately.
• Not a tree. If the input has a cycle or a node with two parents, the DFS either loops or visits nodes twice and answers become arbitrary. Check that n - 1 edges reach n nodes from the root before running.
• Unanswered queries. Count entries left at -1 after the run; they mean an endpoint was never reached.

What to do next

1. Copy the iterative implementation and the brute-force harness, and run the harness with and without union by rank to see that both pass with the correct label rule.
2. Add tests for n = 1, a path of your maximum size, a star, self-queries and a forest.
3. Decide whether your workload is truly offline; if queries come in several batches on the same tree, compare against an Euler tour with a sparse table.
4. Measure memory for your largest query file and switch to offset arrays if bucket lists dominate.
5. If you need distances or bottlenecks, add depths and path aggregates and extend the brute-force check to cover them.