Fast Algorithms for Finding Nearest Common Ancestors

We consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, “What is the nearest common ancester of vertices x and y? ” We show that any pointer machine that solves this problem requires (n) time per query in the worst case, where n is the total number of vertices in the trees. On the other hand, we present an algorithm for a random access machine with uniform cost measure (and a bound of (n) on the number of bits per word) that requires O (1) time per query and O (n) preprocessing time, assuming that the collection of trees is static. For a version of the problem in which the trees can change between queries, we obtain an almost-linear-time (and linear-space) algorithm.