Mehlhorn's LCA Algorithm

Purpose: Kurt Mehlhorn’s contributions to LCA and related tree problems, primarily the union-find based offline LCA presentation and the incremental variant that supports adding leaves between queries.

Offline LCA via union-find

This is the algorithm most often credited to Tarjan and presented in Mehlhorn’s Data Structures and Algorithms textbook, which is where a generation of readers met it.

Process the tree with a DFS. Maintain a DSU where each finished subtree is collapsed into a single set, tagged with the subtree’s root (“ancestor” of the set).

void dfs(int u) {
    make_set(u);
    anc[find(u)] = u;
    for (int v : children[u]) {
        dfs(v);
        unite(u, v);
        anc[find(u)] = u;          // the merged set is still rooted at u
    }
    visited[u] = true;
    for (auto [v, qid] : queries[u])
        if (visited[v]) answer[qid] = anc[find(v)];
}

When we finish $u$ and look at a query $(u,v)$ with $v$ already visited, find(v) gives the set containing $v$, whose tagged ancestor is precisely $\mathrm{LCA}(u,v)$ — because the sets merge exactly along the path from $v$ up to the current position.

Complexity

• Time: $O((n+q)\alpha (n))$ — effectively linear
• Space: $O(n+q)$
• Constraint: all queries must be known before the traversal starts

Incremental / online extensions

Mehlhorn also studied the version where the tree grows — new leaves are added between queries. The union-find approach breaks (the DFS order is no longer fixed), and the answers come instead from:

• maintaining an Euler tour in a balanced BST, so insertions are $O(\log n)$ and LCA is an RMQ over a dynamic sequence; or
• link-cut trees, which give $O(\log n)$ amortized LCA under arbitrary link and cut.

Choosing an LCA method

Situation	Method	Complexity
Static tree, queries known in advance	offline union-find	$O((n+q)\alpha )$
Static tree, online queries	binary lifting	$O(n\log n)$ / $O(\log n)$
Static tree, need $O(1)$ query	Euler tour + sparse table	$O(n\log n)$ / $O(1)$
Static tree, need $O(n)$ preprocess	Farach-Colton-Bender	$O(n)$ / $O(1)$
Tree grows by leaves	Euler tour in a balanced BST	$O(\log n)$
Tree changes by link/cut	link-cut tree	$O(\log n)$ amortized

The offline trick generalises

“Sort the queries so a cheap incremental structure suffices” is a pattern far beyond LCA — it is the same idea behind Mo’s algorithm, offline BIT sweeps, and offline dynamic connectivity. If a problem gives you all queries up front, always ask what becomes easy.

Variants / Use Cases

• Tarjan’s offline LCA — the same algorithm, the usual attribution
• Lowest Common Ancestor — the topic page
• DSU — the structure that makes the offline version near-linear
• Auxiliary tree / virtual tree construction — needs LCA of consecutive nodes in DFS order