Tarjan's Off-Line Lowest Common Ancestors Algorithm

Tarjan's off-line lowest common ancestors algorithm is a graph and tree traversal algorithm in computation and algorithms formulated by Robert E. Tarjan in 1979 (following an earlier 1973 framework by Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman) that answers a predetermined batch of Q lowest common ancestor (LCA) queries on a rooted tree T of N vertices in O((N + Q) α(N)) worst-case time, where α(N) is the inverse Ackermann function. When augmented by the 1985 Gabow–Tarjan microset RAM refinement, the algorithm runs in optimal O(N + Q) linear time.

Unlike on-line LCA data structures (such as heavy–light decomposition, binary lifting, or the Bender–Farach-Colton Euler-tour Range Minimum Query reduction), which must preprocess T so that arbitrary queries arriving one at a time can be answered dynamically, an off-line algorithm receives the entire query set P = { {u₁, v₁}, …, {u_Q, v_Q} } prior to execution. By bucketsorting the query pairs into vertex adjacency lists and performing a single Depth-First Search (DFS) backed by a disjoint-set data structure, Tarjan's algorithm resolves every query {u, v} at the moment the second of the two vertices is visited during DFS.

Definition of Lowest Common Ancestor

Let T = (V, E) be a rooted tree with vertex count N = |V| and designated root r ∈ V.

• A vertex a ∈ V is an ancestor of vertex u ∈ V (written a ≼ u) if a lies on the unique simple tree path from the root r to u (with every vertex being an ancestor of itself).
• A vertex a ∈ V is a common ancestor of u and v if a ≼ u and a ≼ v.
• The lowest common ancestor (or nearest common ancestor), denoted LCA_T(u, v), is the unique common ancestor of u and v that lies at greatest depth (furthest from the root r):

Equivalently, LCA_T(u, v) is the unique vertex where the paths from r to u and from r to v diverge.

DFS Coloring and Equivalence-Class Representatives

Consider a standard recursive Depth-First Search of T starting at the root r. At any instant when the DFS is currently visiting a vertex u, every vertex x ∈ V is in one of three states:

1. Unvisited (White): DFS has not yet entered the subtree T_x rooted at x.
2. Active Ancestor (Gray): DFS has entered T_x but has not yet finished x; such vertices form the active recursion stack r = a₀ → a₁ → … → a_k = u of all ancestors of u.
3. Finished / Post-Order Visited (Black): DFS has completely explored and exited the subtree T_x prior to reaching u.

Suppose that at the moment DFS visits u, we inspect a query pair {u, v} ∈ P in which the partner vertex v has already been visited (so v is either Gray or Black). What is LCA_T(u, v)?

• Case 1 (v is Gray): Because v is currently on the active DFS stack above u, v is an ancestor of u (v ≼ u), so LCA_T(u, v) = v.
• Case 2 (v is Black): Let a = LCA_T(u, v). Because a is an ancestor of the currently active vertex u, a must still be Gray (on the active stack). Conversely, if c is the child of a whose subtree T_c contains v, the DFS must have completely finished exploring T_c (so c and all vertices in T_c are Black) before stepping into the sibling child subtree of a containing u.

Therefore, for every already-visited vertex v, LCA_T(u, v) is the deepest Gray ancestor of v on the current DFS stack. Tarjan observed that if each finished child subtree T_c is merged via a disjoint-set data structure (Union) into its parent a upon backtracking from c to a, and each disjoint set maintains an ancestor pointer to its unique Gray root a, then querying *ancestor*[Find(v)] returns LCA_T(u, v) in near-constant time.

Step-by-Step Recursive DFS + Union-Find Execution

Before starting the traversal, each query {u, v} ∈ P is appended to the query adjacency lists of both u and v (*queries*[u] and *queries*[v]) so it will be examined once when the first endpoint is visited (and ignored because the second endpoint is still unvisited) and resolved when the second endpoint is visited.

For a subtree rooted at u:

1. Initialize Singleton Set: Call MakeSet(u) in the disjoint-set forest, and set *ancestor*[Find(u)] ← u.
2. Recurse on Children and Merge Subtrees: For each child w of u in T:
   • Recursively invoke TarjanLCA(w).
   • Merge w's finished subtree into u's set: Union(Find(u), Find(w)).
   • Re-establish u as the Gray representative of the combined set: *ancestor*[Find(u)] ← u.
3. Mark Visited and Answer Queries: Mark *visited*[u] ← true (coloring u Black/visited). For every partner v in *queries*[u]:
   • If *visited*[v] is true, record the answer for query {u, v} as *ancestor*[Find(v)].

Correctness and Asymptotic Complexity

Within computational complexity theory, the correctness of TarjanLCA follows by induction on the post-order completion steps:

• While DFS is inside u's j-th child subtree T_wj, all vertices in u's previously completed child subtrees T_w1, …, T_wj−1 (as well as u itself) have been united into a single disjoint set whose ancestor attribute points to u.
• More generally, for every ancestor a on the current DFS recursion stack above u, the disjoint set containing a consists of a together with all finished child subtrees hanging off the path from a down to the next ancestor on the stack, and its ancestor attribute equals a.
• When Find(v) is invoked for any visited vertex v, it locates that exact equivalence class and returns a = LCA_T(u, v).

Time and Space Bounds:

• The DFS performs N calls to MakeSet, N − 1 calls to Union, and at most Q calls to Find (one for each resolved query {u, v}).
• Using Disjoint-Set Union with union by rank (or size) and path compression, the total time for N − 1 unions and Q finds on an N-element universe is O((N + Q) α(N + Q, N)).
• In 1985, Harold N. Gabow and Robert E. Tarjan observed that because the union tree topology is known in advance (it is the tree T itself), partitioning T into microtrees of size O(log N) and using word-RAM bitmask lookup tables inside microtrees eliminates the α(N) factor, achieving strict O(N + Q) linear time.

Comparison of Off-Line and On-Line LCA Algorithms

1. Dominator Trees and Compiler Control-Flow Optimization (Lengauer–Tarjan Algorithm): Finding immediate dominators in compiler control-flow graphs and computing static single assignment (SSA) dominance frontiers rely on off-line LCA and path-compression tree evaluations formulated by Tarjan.
2. Phylogenetics and Gene-Species Tree Reconciliation: In evolutionary genomics, reconciling a batch of gene-family trees against a reference species tree to count gene duplications, horizontal transfers, and deep coalescences maps every internal gene-tree node to its LCA in the species tree in linear batch time.
3. Minimum Bottleneck Paths in Spanning and Cut Trees: Given a minimum spanning tree or a Gomory–Hu tree, Tarjan's off-line LCA algorithm (augmented with path-minimum edge aggregation during path compression, Tarjan 1979) verifies minimum spanning trees and answers Q pairwise bottleneck capacity queries in O((N + Q) α(N)) time.

Why is a separate ancestor array needed alongside the Union-Find representative?

When Union(Find(u), Find(w)) merges the set of u with the set of its child w, union by rank may attach u's root under w's root if T_w has higher rank than the current set of u. Therefore, the internal Union-Find root Find(u) is not guaranteed to be the highest tree vertex u; storing *ancestor*[Find(u)] ← u explicitly after each union preserves the correct tree ancestor while allowing union by rank to maintain balanced disjoint-set trees.

How does Tarjan's algorithm handle self-queries {u, u}?

Because *visited*[u] is set to true right before iterating over *queries*[u] (and *ancestor*[Find(u)] = u), a query pair {u, u} immediately evaluates *visited*[u] as true and returns *ancestor*[Find(u)] = u.

1. Tarjan, R. E. (1979). "Applications of path compression on balanced trees." Journal of the ACM, 26(4), 690–715. https://doi.org/10.1145/322154.322161
2. Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1976). "On finding lowest common ancestors in trees." SIAM Journal on Computing, 5(1), 115–132. https://doi.org/10.1137/0205011
3. Gabow, H. N., & Tarjan, R. E. (1985). "A linear-time algorithm for a special case of disjoint set union." Journal of Computer and System Sciences, 30(2), 209–221. https://doi.org/10.1016/0022-0000(85)90014-590014-5)
4. Harel, D., & Tarjan, R. E. (1984). "Fast algorithms for finding nearest common ancestors." SIAM Journal on Computing, 13(2), 338–355. https://doi.org/10.1137/0213024