Lowest Common Ancestor Queries

Let T be a rooted tree. The lowest common ancestor of any pair of nodes u_i,u_j in T is their common ancestor that is farthest away from the root.


For example, in the graph shown in this figure, the lowest common ancestor of u6 and u10 is u3.


In the lowest common ancestor queries problem, given a tree you need to pre-process the information such as to provide O(1) per-query answers to the question "What is the lowest common ancestor" of nodes ui and uj for any i,j in [n].
Assume for simplicity that the tree is a binary tree.
Then construct the following structures:


-An array E[1..2n-1] that stores the nodes of T in the order in which they occur in the Euler leftmost-way tour of the "double-tree" obtained from doubling each edge of T, starting at the root.


-An array L[1..2n-1] such that L[i] stores the level of node E[i].


-An array R[1..n] such that R[i] is the smallest integer l for which E[l] = ui.


Then for a given pair i, j assuming R[i] < R[j]. Let k be the integer such that R[i] ≤ k ≤ R[j] and L[k] is minimum. Then the lowest common ancestor of nodes ui and uj is equal to E[k].


Finding L[k] that is minimum for the subarray L[i..j] can be done in O(1) time if you apply the O(n log n) preprocessing used in this post to find the range minimum queries problem.


MArio