Harel-Tarjan LCA Algorithm

Purpose: The first $O(n)$-preprocessing, $O(1)$-query algorithm for Lowest Common Ancestor (1984) — the result that established LCA as a constant-time operation.

The Idea: compressed trees and bit tricks

1. Heavy path decomposition. Partition the tree into paths so that any root-to-leaf walk crosses $O(\log n)$ paths. (The same decomposition later popularised as HLD.)
2. Complete binary tree embedding. Map the compressed structure into a complete binary tree, where LCA has a closed form: for nodes with inorder labels $x$ and $y$, the LCA label is obtained from the highest bit where $x$ and $y$ differ — a single XOR and a clz.
3. Bit-encoded ancestor sets. Each node stores a machine word whose bits record which of the $O(\log n)$ path levels contain an ancestor. Combining two such words with bitwise operations locates the correct path in $O(1)$.

Queries become a fixed sequence of shifts, XORs and leading-zero counts — no lookups into large tables.

Complexity

• Preprocessing: $O(n)$
• Query: $O(1)$
• Space: $O(n)$ words

Historical significance

Before Harel-Tarjan, LCA was thought to require a logarithmic factor. Their paper showed constant time was achievable and triggered a sequence of simplifications:

Year	Result	Approach
1984	Harel-Tarjan	compressed trees + bit tricks; correct but hard
1988	Schieber-Vishkin	simplified, parallelisable, still bit-trick based
1993	Berkman-Vishkin	reduction to ±1 RMQ
2000	Farach-Colton-Bender	±1 RMQ + four Russians; the standard exposition
2004	Bender-Farach-Colton	further simplification, sparse table on blocks
—	Tarjan offline	$O((n+q)\alpha )$ with DSU, if queries are known in advance

What to actually use

Need	Use
LCA only, simple code	Euler tour + sparse table — $O(n\log n)/O(1)$
LCA + $k$-th ancestor + path aggregates	Binary lifting — $O(n\log n)/O(\log n)$
All queries known in advance	Tarjan offline
Path updates and queries	HLD + segment tree
Truly need $O(n)$ preprocessing	Farach-Colton-Bender

In practice, binary lifting is the right default: it is 20 lines, and $O(\log n)$ per query is never the bottleneck.

Variants / Use Cases

• Lowest Common Ancestor — the topic page with code
• Level ancestor problem — a related $O(n)/O(1)$ result (Bender-Farach-Colton, via ladder decomposition)
• Distance in trees — $\mathrm{dist}(u,v)=d_u+d_v-2d_{\mathrm{lca}}$; the single most common use of LCA
• HLD — the decomposition Harel and Tarjan introduced here, now famous for a different reason