The least common ancestor of two nodes u and v in a rooted tree T is depth in T. In the off-line least-common ancestor problem, we are given a rooted tree T and an arbitrary set P = {(u,v)) of unordered pairs of nodes in T, and we wish to determine the least common ancestor of each pair in P. To solve the off-line least-common ancestor problem, the following proce- dure performs a tree walk of T with the iniital call LCA (r) where r is the