Tarjan's Offline LCA Algorithm: A Practical Tutorial for Tree Queries

Tarjan's offline lowest common ancestor algorithm is one of those elegant techniques that quietly powers countless tree-query systems behind the scenes. When you need to answer many ancestry questions over a static tree, processing them all at once rather than one by one, the method attributed to Robert Tarjan from the late 1970s remains remarkably efficient. It sidesteps the complexity of heavy data structures like link-cut trees while still delivering near-linear performance.

The core idea is deceptively simple. After building the tree and reading every query pair upfront, a single depth-first search combines a union-find structure with ancestor tracking to resolve all pairs in one pass. For students studying competitive programming in Sydney or Brisbane, the algorithm is a staple of university courses at places like UNSW and the University of Melbourne. It appears in national contests and coding interviews across Australia because it rewards clear thinking rather than rote memorisation.

There is a satisfying rhythm to tracing the recursion by hand. Each node is marked, queries involving it are checked against the marked set, and unions merge sibling subtrees. The result is that the algorithm runs in O((n + q) α(n)) time, where α is the inverse Ackermann function, making it effectively linear for practical sizes. In Australian competitive programming circles, where query counts can reach hundreds of thousands on trees of similar size, that scaling matters.

This tutorial walks through the algorithm step by step. We start with the problem itself, contrast offline and online strategies, dissect the mechanics of the union-find dance, then move into pseudocode and a concrete Python implementation. Along the way, we will point out the subtle choices that make the difference between a working solution and one that quietly produces wrong answers on edge cases.

The Lowest Common Ancestor Problem

The lowest common ancestor of two nodes in a rooted tree is the deepest node that lies on the paths from the root to each of them. If one node is an ancestor of the other, that ancestor is itself the answer. The query appears everywhere from version control systems that reconcile branches to biological phylogenetics and the routing logic of content delivery networks serving traffic across Australian data centres in Canberra and Perth.

Formally, given a rooted tree with n nodes and q queries, each query asks for LCA(u, v). The naive approach walks upward from u and v simultaneously, marking ancestors until a match appears. That costs O(height) per query, which becomes painful on deep trees. Many real trees are reasonably shallow, but problems arising from file system hierarchies or organisational charts in large Australian companies often have deeply unbalanced shapes, so worst-case behaviour matters.

A common misconception is that the problem requires a data structure like a segment tree or a balanced BST. Those tools are useful for other range queries, but for ancestry problems, the structure of the tree itself provides most of the answer. Recognising this lets us choose algorithms tailored to the topology rather than reaching for general-purpose machinery. Choosing the right tool mirrors the kind of thinking behind understanding the bias-variance tradeoff in machine learning, where the right complexity depends on the structure of the data.

Offline vs Online Approaches

Online LCA algorithms answer each query as it arrives, with no knowledge of future requests. The Euler tour plus sparse table method sits in this category: preprocess in O(n log n), then answer each query in O(1). The offline world, by contrast, lets you read the entire query list before producing a single answer. Tarjan's method belongs firmly to the offline camp.

Why choose offline? The big advantage is that you only traverse the tree once. The DFS does double duty, both exploring structure and resolving queries as it backtracks. For batch processing workloads, such as computing similarities across a corpus of Australian news articles archived in a tree of topics, this is a natural fit. For interactive systems where the user types queries one at a time, online methods are easier to deploy.

The trade-off mirrors other classic engineering tensions: memory for speed, simplicity for flexibility, locality for latency. Each algorithm has its place. Tarjan's shines when the tree is fixed, queries are abundant, and you can afford to hold them all in memory. That description matches most interview problems, many contest problems, and a long tail of real-world pipelines that analyse graph snapshots taken at regular intervals.

The offline nature also makes parallelisation more straightforward. Since all queries are known, you can distribute them across workers, each running its own DFS on a shared union-find structure protected by locks. In cloud regions like ap-southeast-2 in Sydney, distributed LCA computation becomes feasible when the tree is large enough to justify the orchestration cost.

How Tarjan's Algorithm Works

Tarjan's algorithm maintains three things during a DFS: a visited marker for each node, a union-find data structure that groups nodes by their current ancestor, and a list of queries for the current node. When the DFS visits a node u, it first recurses into every child v. After returning from v, the union-find operation merges the set containing v into the set containing u, recording u as the ancestor of that union.

When all children have been processed, u is marked. Then, for every query (u, w) or (w, u) where w has already been marked, the answer is the ancestor of the set containing w, found via union-find. The intuition is that w's ancestor in the union-find structure points exactly to the deepest ancestor of u that is also an ancestor of w. Because the DFS has explored every node on the path from the root to w before reaching u's post-processing stage, that ancestor is exactly LCA(u, w).

A subtle point is the order of operations. The union of a child's set into the parent's set must happen after the child's recursion completes but before the parent is marked. Getting this order wrong is a common source of bugs, especially when adapting code from one language to another. Many students at the University of Sydney first learn this algorithm by debugging exactly this mistake on a whiteboard in a tutorial room overlooking the harbour.

The visited marker is what enables the final lookup. Without it, queries involving nodes not yet reached would resolve to the root, which is correct in some degenerate cases but wrong in general. The marker guarantees that we only answer queries between nodes whose mutual ancestor relationship is fully resolved by the current state of the traversal.

Pseudocode and Complexity

Here is the standard pseudocode, presented in a form close to what you might see in a textbook or a competitive programming slide deck.

function tarjan_lca(u, parent):
    make_set(u)
    ancestor[u] = u
    for v in children(u):
        if v != parent:
            tarjan_lca(v, u)
            union(u, v)
            ancestor[find(u)] = u
    colour[u] = black
    for each query (u, w):
        if colour[w] == black:
            answer(u, w) = ancestor[find(w)]

The union-find structure with path compression and union by rank gives amortised α(n) per operation. The DFS visits each node and edge once, contributing O(n + q) work for the traversals and query checks. The overall complexity is O((n + q) α(n)), which in practice behaves like linear time.

The space cost is O(n) for the tree, the union-find arrays, and the query storage. Holding all q queries in memory is the main limitation for truly massive inputs, but for trees with up to several hundred thousand nodes and similar query counts, modern laptops used by Australian contestants at events like the Australian Informatics Olympiad handle the workload comfortably.

Choosing α(n) over a log factor matters more than it might seem. On a tree with a million nodes, log n is around 20, while α(n) is essentially 4. Over millions of operations, that gap compounds. The difference between an O(n log n) solution and an O(n α(n)) solution can decide whether a submission clears the time limit on a contest judge's hardware.

Implementation Walkthrough

A clean Python implementation makes the algorithm concrete. Start by building the tree as an adjacency list and storing the queries as a map from each node to the list of its partners. The union-find structure uses parent and rank arrays, with a separate ancestor array tracking the representative's current ancestor.

The DFS function takes the current node and its parent. For each child, the function recurses, unions the child's root into the current node's root, and updates the ancestor of the new root. After all children are processed, the node is marked black. Then, for every query partner that is already marked, the answer is fetched via a find operation.

One practical tip is to use iterative DFS rather than recursion if the tree is very deep, since Python's recursion limit defaults to around 1000. For trees representing real organisational structures at an Australian bank or telecom, depths can easily exceed that. Either raise the limit with sys.setrecursionlimit or convert to an explicit stack-based version.

Once the algorithm is working, the natural next step is exposing it through a small library or API. For practitioners who want to integrate tree-query logic into a web service, the web development resources section of hello ML offers useful patterns for packaging algorithmic code into endpoints. From there, LCA queries can power features like permission hierarchies, taxonomy navigation, or ancestry views in collaborative tools built by teams in Melbourne's vibrant startup scene.

Testing deserves attention as well. Build a brute-force reference that walks both paths upward and compare results across random trees and random query batches. Random generation tends to surface off-by-one errors in tree construction and edge cases in union-find initialisation far more efficiently than hand-written test cases. Thousands of randomised runs build real confidence in the implementation before it touches production data.