Tarjan's Offline LCA

Pick any two nodes in a tree — say node 7 and node 11. Their lowest common ancestor (LCA) is the deepest node that is an ancestor of both: the point where their two paths up to the root converge.

LCA is everywhere in practice: it drives distance queries between nodes (the distance from u to v equals $\text{depth}(u) + \text{depth}(v) - 2\cdot\text{depth}(\text{LCA}(u,v))$), it underlies compiler control-flow analysis, and it powers database query optimizers working on hierarchical data. The question comes up not once, but in bulk: you have a tree with n nodes and q pairs, and you need all q answers.

The naive approach queries each pair independently. The most basic method — walk up from each node until the paths meet — costs O(depth) per query, which is $O(n)$ on a skewed tree. A classic binary lifting table brings each query to $O(\log n)$, so q queries cost $O(q \log n)$. That is good, but it still grows with both n and q.

Robert Tarjan's offline algorithm (1979) blows past that bound. If you are willing to collect all q queries first and answer them together rather than on-demand (that is, "offline"), a single DFS over the tree — enhanced with a Union-Find structure — resolves every query in $O(n + q \cdot \alpha(n))$ total time, where $\alpha$ is the inverse Ackermann function, effectively a constant in any realistic setting. For large batches that savings is enormous.

The demo below builds an 11-node tree and loads 5 batch LCA queries. Click Step to advance Tarjan's DFS one node at a time, or Run all to watch the full sweep. Answered queries light up immediately as the DFS visits their nodes.

<p class="hint">{{hint}}</p>
<div class="layout">
  <svg id="tree-svg" viewBox="0 0 340 240" width="340" height="240"></svg>
  <div class="panel">
    <div class="panel-title">{{panel_queries}}</div>
    <div id="query-list"></div>
    <div class="panel-title" style="margin-top:.7rem">{{panel_log}}</div>
    <div id="log"></div>
  </div>
</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: .8rem; align-items: flex-start; flex-wrap: wrap; }
#tree-svg { flex-shrink: 0; }
.panel { flex: 1; min-width: 160px; font-size: .83rem; }
.panel-title { font-weight: 700; font-size: .78rem; text-transform: uppercase;
               letter-spacing: .04em; color: #555; margin-bottom: .25rem; }
#query-list { display: flex; flex-direction: column; gap: .22rem; }
.qrow { padding: .2rem .4rem; border-radius: 5px; background: #eef1f5;
        border: 1px solid #d0d8e4; display: flex; gap: .4rem; align-items: center; }
.qrow.answered { background: #d4edda; border-color: #82c491; }
.qrow .qlabel { font-weight: 600; flex: 1; }
.qrow .qans { color: #1a7d3e; font-weight: 700; }
#log { font-size: .78rem; color: #333; max-height: 130px; overflow-y: auto;
       background: #f7f8fb; border: 1px solid #dde3ec; border-radius: 5px;
       padding: .3rem .5rem; }
.log-line { line-height: 1.5; }
.log-enter { color: #1d3557; }
.log-leave { color: #6a0572; }
.log-answer { color: #1a7d3e; font-weight: 600; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.node circle { stroke-width: 1.6; }
.node text { font: 600 11px system-ui, sans-serif; pointer-events: none; }
.edge { stroke: #b0bec5; stroke-width: 1.6; fill: none; }

// Code not found

Notice that every query is answered exactly once, at the moment the DFS finishes processing one of the two queried nodes and the other has already been visited (so its ancestor set is tracked by Union-Find). No node is ever revisited. The algorithm is gloriously efficient: the total work is proportional to the size of the tree plus the number of queries — nothing more.

Status: solved — Tarjan published the offline LCA algorithm in 1979. It is a provably optimal offline algorithm for the problem.

The algorithm works in three phases:

1. Preprocessing — Collect all q query pairs and group them by node: for each node u, store the list of queries that involve u.
2. DFS sweep — Perform a single depth-first traversal of the tree. When the DFS enters node v, create a new Union-Find set for v (its "ancestor set"). When the DFS finishes all children of v and backtracks, merge v's set into its parent's set, making the parent the canonical representative of the merged set. At this moment, any query (u, v) where u has already been fully visited is answered: LCA(u, v) = Find(u) — the current root of u's ancestor set.
3. Query answers — Each query is answered at most once, in $O(\alpha(n))$ time per Find operation.

Total cost: $O(n)$ for the DFS + $O(q \cdot \alpha(n))$ for all Find calls = $O(n + q \cdot \alpha(n))$, practically linear.

Why does Find(u) return the correct LCA? Because Union-Find tracks which subtree has been fully processed. When node v finishes, all of v's subtree is merged upward. So Find(u) at that moment returns the deepest ancestor of v that is also an ancestor of u — exactly the LCA.

Compared to alternatives:

The Farach-Colton–Bender algorithm (2000) later achieved true $O(1)$ per query online, but Tarjan's offline approach remains the classic for batch workloads because it is remarkably simple to implement correctly. See also minimum spanning tree for another setting where Union-Find produces an elegant linear bound.

Answering many ancestor queries at once turns out to be fundamental to a surprising range of fields:

• Tree distances in bulk: The identity dist(u, v) = depth(u) + depth(v) − 2·depth(LCA(u,v)) means any batch of distance queries on a weighted tree reduces directly to a batch of LCA queries — Tarjan's algorithm answers all of them in one pass.
• Compiler control-flow analysis: Dominators in a control-flow graph — which nodes must be visited before any path to a target — can be computed with LCA queries on a DFS tree. Tarjan used his own algorithm in compiler backends.
• Bioinformatics and phylogenetics: Given a phylogenetic tree with thousands of species, biologists routinely need the most recent common ancestor of many pairs. A single offline sweep handles all pairs in linear time.
• XML and document processing: Hierarchical documents (HTML, JSON, file systems) support "find nearest common container" queries, which are exactly LCA on the document tree.
• Network routing: Shortest paths in tree-structured networks (spanning trees of the internet backbone) rely on fast LCA to find the meeting point of two routes.

Union-Find — the workhorse inside Tarjan's algorithm — appears across algorithms wherever disjoint sets need to be merged and queried efficiently. See also dynamic shortest paths for related tree-manipulation techniques.

Tarjan's offline LCA algorithm distills a powerful idea: batching pays off. Instead of answering each ancestor question the moment it arrives, gather all of them, then sweep the tree once — and let the DFS + Union-Find machinery answer every query at exactly the right instant during the traversal.

The result is near-linear total time regardless of how many queries there are, making it one of the most cost-efficient tricks in classical algorithmics. The algorithm is not merely a theoretical curiosity; it is implemented in competitive programming libraries, compiler toolchains, and bioinformatics pipelines worldwide.

The next time you need to answer thousands of ancestor or distance queries on a tree, remember: collecting them first and sweeping once is almost always faster than handling each one independently.