Tarjan's off-line least common ancestors algorithm

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 = {{d,e}} 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.