Tarjan's off-line least common ancestors algorithm

In computer science, Tarjan's off-line least common ancestors algorithm is an algorithm based on the least common ancestor property.

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.