The least common ancestor of two nodes d and e in a rooted tree T is the node g that is an ancestor of both d and e and that has the greatest depth in T.
The off-line least common ancestors problem gives us a rooted tree T and a set P = of unordered pairs of nodes in T.
Tarjan's off-line least common ancestors algorithm determines the least common ancestor of each pair in P.
An example of the algorithm:
TOLCA(u) {
Make-set(u);
ancestor[Find-Set(u)] <- u;
for each child v in u in T
do { TOLCA(v);
Union(u,v);
ancestor[Find-Set(u)] <- u;
}
colour[u] <- black;
for each node v such that {u,v} in P
do if (colour[v] = black) {
print "Tarjan's Least Common Ancestor of" + u + " and " + v + " is " ancestor[Find-Set(v)];
}
}
The following procedure assumes each node is white before coloured black.