The least common ancestor of two nodes u and in a rooted tree T is the

The least common ancestor of two nodes u and ν in a rooted tree T is the node w that is an ancestor of both u and ν and that has the greatest depth in T. In the off-line least-common-ancestors problem, we are given a rooted tree T and an arbitrary set P = {{u, ν}} 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-ancestors problem, the following procedure performs a tree walk of T with the initial call LCA (T.root). We assume that each node is colored WHITE prior to the walk.

LCA (u)

a. Argue that line 10 executes exactly once for each pair {u, ν} ∈ P.

b. Argue that at the time of the call LCA (u), the number of sets in the disjoint-set data structure equals the depth of u in T.

c. Prove that LCA correctly prints the least common ancestor of u and ν for each pair {u, ν} ∈ P.

d. Analyze the running time of LCA, assuming that we use the implementation of the disjoint-set data structure in Section 21.3.