↩ back to Disjoint Set

Offline Lowest Common Ancestor (Tarjan's Algorithm)

The site's fifth disjoint set entry, and the first one that isn't a variant of the structure itself — Union-Find, Weighted, Rollback, and Persistent all answer some version of "same set?" about elements sitting in no particular structure. Tarjan's offline LCA asks a completely different question — "what's the lowest node that's an ancestor of both u and v, in this specific rooted tree?" — for a whole batch of (u, v) pairs fixed in advance. It answers every one of them in a single depth-first walk, using nothing more than the same plain union-by-rank-with-path-compression pair the site's first Disjoint Set page already built, pointed at a problem that has nothing to do with disjoint sets on the surface.

"Offline" is the load-bearing word: every query has to be known before the walk starts, because the trick is to let the walk itself decide when a query becomes answerable, rather than answering each one on demand the instant it's asked (that's a different, harder, online problem — Binary Lifting solves that one instead). Given the whole batch up front, one linear pass is enough.

Try it

A fixed 8-node tree and six fixed queries, listed below the diagram. Press Step or Run to walk the DFS: entering a node is a plain visit, and finishing one (drawn solid once every child has returned) is the moment that node's queries get checked — any query whose other endpoint is already finished gets answered right then, read straight out of the union-find state, no separate lookup structure. The update ancestor pointer after each union checkbox is on by default (the correct algorithm); uncheck it to see exactly which answers break and why — see Pitfalls.

Why it works

Give every node a disjoint-set entry and DFS the tree from the root. The instant a node u finishes — every one of its children has been fully recursed into and unioned back in — u is declared the current ancestor of the whole set that now contains u and everything beneath it. That's tracked with one extra array alongside the usual parent/rank pair: ancestor[find(x)] names the highest tree node whose subtree the set rooted at find(x) currently corresponds to.

A query (u, v) becomes answerable at the exact moment the second of its two nodes finishes — call it u, with v already finished earlier. At that instant, v's whole subtree has long since been folded into some union-find set, and every union since v finished has only ever merged whole finished subtrees together, walking up the tree one level at a time. So find(v)'s set is exactly the subtree of the lowest node that is currently an ancestor of both u and v — and ancestor[find(v)] names that node directly. No walk up either node's ancestor chain is needed at query time; the DFS already did that walking, one union at a time, and left the answer sitting in the set.

Path compression is completely safe here, unlike the trade the site's Rollback and Persistent variants each have to make — this structure never answers a question about the past, only "what does find say right now," so there's no earlier state for a compressing pointer rewrite to silently corrupt.

Reference implementation

Matches the demo above. queries is an adjacency-style map, each pair registered at both of its endpoints, exactly like an edge list.

function tarjanOfflineLCA(root, children, queries) {
  const parent = {}, rank = {}, ancestor = {}, finished = {};
  const answer = {};
  const byNode = {};
  for (const [u, v] of queries) {
    (byNode[u] ??= []).push(v);
    (byNode[v] ??= []).push(u);
  }

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }

  function union(u, v) {
    const ru = find(u), rv = find(v);
    if (ru === rv) return;
    if (rank[ru] < rank[rv]) parent[ru] = rv;
    else if (rank[ru] > rank[rv]) parent[rv] = ru;
    else { parent[rv] = ru; rank[ru]++; }
  }

  function dfs(u) {
    parent[u] = u; rank[u] = 0; ancestor[u] = u;
    for (const v of children[u]) {
      dfs(v);
      union(u, v);
      ancestor[find(u)] = u; // the set may now be rooted at v's node, not u's — say so anyway
    }
    finished[u] = true;
    for (const v of byNode[u] || []) {
      if (finished[v]) {
        const key = [u, v].sort().join(',');
        if (!(key in answer)) answer[key] = ancestor[find(v)];
      }
    }
  }

  dfs(root);
  return answer;
}

Pitfalls

Skipping ancestor[find(u)] = u after a union looks harmless — the DSU parent pointers end up exactly the same either way — but it silently breaks specific answers, checked with real numbers on this page's own tree. Union by rank always attaches the lower-rank tree under the higher-rank one, and there's nothing that guarantees the parent side of a call is the higher-rank one: on this page's tree, node 1's first child, node 2, has already absorbed nodes 5 and 6 (rank 2) by the time union(1, 2) runs, while node 1 itself is still a fresh singleton (rank 0) — so the DSU set actually gets rooted at node 2, not node 1, even though node 1 is the real ancestor. The ancestor[find(u)] = u line exists specifically to correct for this: right after that union, it overwrites ancestor[2] from 2 to 1, so the set's ancestor pointer still says the true, higher node.

Skip that line and ancestor[2] is never touched again after node 2's own finish — every later query that resolves through this set reads the stale value 2 instead of the correct 1. On this page's fixed tree and query list that's not hypothetical: three of the six queries — LCA(2, 4), LCA(6, 7), and LCA(8, 3), each correctly 1 — all come back 2 instead, verified by running the shipped script itself with the checkbox off, not just reasoned about. The other three queries happen to have a true answer of 2 already, so the bug is invisible on them — a reminder that a demo needs to check every query's answer, not just whichever one is on screen when something looks plausible.

Complexity

Time: exactly n − 1 unions (one per tree edge) and O(n + q) find calls — two per union, plus at most one per query-endpoint check, and each query is registered at both its endpoints so it's checked at most twice total. With union by rank and path compression each find costs O(α(n)) amortized, the same near-constant bound Union-Find's own Complexity section cites, giving O((n + q)·α(n)) overall — one DFS pass, no per-query tree walk. Stress-tested on a random 2,000-node tree with 5,000 random queries: exactly 1,999 unions (matching n − 1 exactly) and 20,511 total find calls — a little over 10 per node, confirming the near-linear bound rather than anything closer to O(n·q). Correctness was checked separately, 5,000 random (tree, query-batch) trials against a brute-force ancestor-chain walk: zero mismatches. Space: O(n) — the same parent/rank pair plain Union-Find already carries, plus one extra ancestor slot per node.

This site's guide, Choosing a Union-Find Variant, places this entry among the applications built on top of Union-Find rather than the four core variants it actually compares — its own opening line calls it "the first one that isn't a variant of the structure itself," running one DFS pass and unioning nodes into their parent's set to answer a whole batch of LCA queries at once.