Wait, What?
A batch of tree-ancestor questions can become easier if you are allowed to answer them later.
The lowest common ancestor problem asks for the deepest node that is an ancestor of two given nodes in a rooted tree. Tarjan’s offline LCA algorithm becomes powerful because it changes the timing contract: all queries are known in advance, so the algorithm can answer them during one depth-first traversal while maintaining disjoint sets.
For learners, this is a rich algorithm because it connects rooted-tree structure, DFS states, union–find, path compression, invariants and the difference between online and offline computation.
Quick Answer
Learn Tarjan’s offline LCA in this order: ancestor relationships → LCA definition → offline query model → DFS traversal → disjoint-set union → ancestor label per set → mark completed nodes → answer a query when its partner is completed → complexity → online/offline trade-offs. The heart of the algorithm is not “use DSU.” It is knowing what each DSU set represents at a particular moment in the DFS.
1. What Is the Lowest Common Ancestor?
In a rooted tree, node x is an ancestor of node y if x lies on the path from the root to y. For nodes u and v, their lowest common ancestor is the common ancestor with greatest depth.
If one node is an ancestor of the other, that ancestor can itself be the LCA.
2. Why “Offline” Changes the Problem
An online algorithm must be ready for a new LCA query after preprocessing the tree. Tarjan’s offline method assumes the complete set of query pairs is available before traversal begins.
That lets us attach each query to both endpoint nodes and postpone its answer until enough of the tree has been processed.
This is a recurring systems idea: if requests can be batched, reordering work may unlock a simpler or faster algorithm.
3. The DFS Gives a Natural Timeline
Run depth-first search from the root. A node passes through useful conceptual states:
- not yet visited;
- active while its descendants are being explored;
- completed after its subtree is finished.
When a subtree is completed, the algorithm merges its DSU set upward into its parent’s set.
4. What the Disjoint Sets Mean
Disjoint-set union normally answers “which component does this element belong to?” Here its meaning is more specialised.
During the DFS, completed subtrees are progressively merged into the set representing their nearest still-relevant ancestor. Each DSU representative has an associated ancestor label telling us which tree node currently represents that set for LCA purposes.
The DSU structure is therefore not merely grouping arbitrary nodes. It is compressing already-processed tree regions while preserving the ancestor we need.
5. The Core Sequence at a Node
For a node u:
make_set(u)
ancestor[find(u)] = u
for each child v of u:
dfs(v)
union(u, v)
ancestor[find(u)] = u
mark u completed
for each query (u, w):
if w is completed:
answer = ancestor[find(w)]The order is crucial. Child sets are merged only after each child subtree has been fully processed.
6. Why the Ancestor Label Must Be Reset After Union
Union-by-rank or union-by-size may choose either root as the physical DSU representative. That physical choice is an implementation optimisation and has no reason to equal the logical tree ancestor.
So after merging child v into parent u, we explicitly restore:
ancestor[find(u)] = uThis separates two concepts professionals must keep distinct:
- DSU representative: chosen for data-structure efficiency;
- logical ancestor label: chosen by tree semantics.
7. When Is a Query Safe to Answer?
Suppose the current node is u and there is a query (u,v). If v has already been completed, then the processed DSU set containing v has already been merged upward as far as the DFS state permits.
At that moment, the label:
ancestor[find(v)]is exactly the lowest common ancestor of u and v.
The completion test prevents us from answering too early while the other endpoint’s subtree is still structurally unresolved.
8. Build the Query Adjacency Structure First
For each query (u,v), store a record at both u and v:
queries[u].append((v, query_id))
queries[v].append((u, query_id))Then when DFS reaches either endpoint, it can inspect only the queries incident to that node rather than scan the entire query list.
This is one reason the total work can remain close to linear in the number of nodes plus queries.
9. A Small Example
Imagine a rooted tree:
A
/ \
B C
/ \ / \
D E F GQueries:
- (D,E) → B
- (D,G) → A
- (F,G) → C
- (B,E) → B
As DFS completes D, E and then B, their sets merge upward. When one endpoint of a query is completed and the other endpoint later becomes current/completed, the DSU label identifies the correct meeting ancestor.
For study, draw the DSU groups after every child return. That picture is much more informative than reading code line by line.
10. The Key Invariant
After a child subtree of u has been completed and unioned into u, every completed node in that subtree belongs to a DSU set whose ancestor label is u, unless that set has later been merged farther upward.
This invariant is what turns find(v) from a generic component lookup into an LCA answer.
11. Why Path Compression Helps Without Breaking Meaning
Path compression changes parent pointers inside the DSU forest to make future find operations faster. It does not change which elements belong to the set.
Because logical ancestry is stored separately in ancestor[representative], the internal shape of the DSU forest is free to change for efficiency.
This is a beautiful separation of concerns: representation can be optimised aggressively as long as the semantic label is maintained correctly.
12. Complexity
The DFS visits every tree edge once. Each child produces a union operation, and each answered query produces find operations. With standard union-by-rank/size and path compression, DSU operations are amortised extremely close to constant time, commonly expressed using the inverse Ackermann function α(n).
Many teaching references summarise the overall method as O(n+m) for n nodes and m queries, suppressing the tiny inverse-Ackermann factor or using refinements that achieve linear bounds in the relevant model.
The practical message is simpler: for a large fixed batch of LCA questions, the total work is essentially linear.
13. Offline Is Not Automatically Better
Tarjan’s method is excellent when:
- the tree is known;
- the query batch is known in advance;
- answers can wait until traversal.
If queries arrive later one by one, preprocess-and-answer methods such as binary lifting, Euler-tour/RMQ approaches or other LCA structures may be more appropriate.
Algorithm choice therefore depends on the interaction pattern, not only asymptotic notation.
14. Recursive DFS Can Become a Systems Issue
A textbook recursive implementation is elegant, but a very deep tree can overflow a language runtime’s call stack. Production code may need an explicit stack that simulates enter-child-return-exit events.
When converting to an iterative traversal, preserve the exact moments when:
- a node’s singleton set is created;
- a child is completed;
- union occurs;
- the ancestor label is restored;
- the node becomes completed;
- queries are checked.
15. Common Failure States
- Answering a query before the opposite endpoint is completed.
- Forgetting to add each query to both endpoints.
- Assuming the DSU representative node itself is automatically the LCA.
- Forgetting to reset ancestor[find(u)] after union.
- Mixing the visited, active and completed states.
- Applying an undirected DFS without preventing movement back to the parent.
- Using recursive DFS on an adversarially deep tree without considering stack limits.
16. Tests That Expose Real Bugs
- single-node tree with query (root,root);
- chain-shaped tree;
- star-shaped tree;
- balanced tree;
- ancestor/descendant query;
- two nodes in the same small subtree;
- nodes in opposite root branches;
- duplicate queries;
- large batches compared against a slower reference implementation.
Property testing can compare every result with a simple parent-climb or binary-lifting reference on randomly generated small trees.
17. Practice Ladder: Beginner to Professional
- Beginner: identify LCAs by eye on small rooted trees.
- Foundation: trace DFS enter/exit order and mark when a node is completed.
- Intermediate: implement union–find separately and explain find, union, path compression and union by rank.
- Advanced: combine DFS and DSU, maintaining the ancestor label after every merge.
- Professional: convert the traversal to iterative form, preserve query IDs, test deep trees, and compare the offline method with binary lifting or Euler-tour/RMQ under different workload patterns.
- Transfer: explain why batching changes the algorithmic design space.
18. A Better Way to Study This Algorithm
Use a state table with columns DFS event → DSU sets → ancestor label → completed nodes → queries now answerable. Predict the next row before executing code. This follows programming-education evidence that tracing and prediction support program comprehension better than passive code reading.
Then use a faded worked example: first provide all DSU states, later hide the ancestor labels, then hide the unions, and finally ask the learner to reconstruct the whole traversal. The goal is to make the invariant retrievable, not the syntax.
Learning Hall Boundary
This article owns Tarjan’s offline LCA method as the union–find solution for a known batch of rooted-tree ancestor queries. It complements existing heavy-light decomposition and Cartesian-tree/RMQ material rather than replacing them. It does not take over general DSU ownership, MindOS learning-process ownership, Bolt measurement jobs or Student/Studying Interface workflow guidance.
Evidence Boundary
MIT CSAIL’s Algorithm Wiki records Tarjan’s offline LCA among the core lowest-common-ancestor algorithms: MIT Algorithm Wiki. Algorithms for Competitive Programming provides a clear implementation-oriented account of Tarjan’s offline method: Tarjan offline LCA, with the companion DSU article explaining path compression and union strategies: DSU. The broader LCA literature includes Dov Harel and Robert E. Tarjan’s work on nearest common ancestors: SIAM record. The learning design also draws on programming-education research on code tracing, subgoal-labelled worked examples, PRIMM and debugging instruction.
Professional rule: you understand Tarjan’s offline LCA algorithm when you can say what a DSU set means at every DFS stage, explain why ancestor[find(v)] is valid only after the opposite endpoint is completed, and choose an offline or online LCA method from the workload contract rather than from habit.
