Lowest Common Ancestor

Question

I am looking for constant time implementation of lowest common ancestor given two nodes in full binary tree( parent x than child 2*x and 2*x+1).

My problem is that there are large number of nodes in the tree and many queries. Is there a algorithm, which preprocesses so that queries can be answered in constant time.

I looked into LCA using RMQ, but I can't use that technique as I can't use array for this many nodes in the tree.

Can some one give me efficient implementation of the algorithm for answering many queries quickly, knowing it is full binary tree and the relation between nodes is as given above.

What I did was to start with two given nodes and successively find their parents ( node/2) keep hash list of visited nodes. when ever we reach a node that is already in hash list, than that node would be the lowest common ancestor.

But when there are many queries this algorithm is very time consuming, as in worst case I may have to traverse height of 30(max. height of tree) to reach root( worst case).

Answer 1

If you represent the two indices in binary, then the LCA can be found in two steps:

1. Shift right the larger number until the leading 1 bit is in the same place as the other number.
2. Shift right both numbers until they are the same.

The first step can be done by getting log base 2 of the numbers and shifting the larger number right by the difference:

if a>b:
    a = shift_right(a,log2(a)-log2(b))
else:
    b = shift_right(b,log2(b)-log2(a))

The second step can be done by XORing the resulting two numbers and shifting right by the log base 2 of the result (plus 1):

if a==b:
    return a
else:
    return shift_right(a,log2(xor(a,b))+1)

Log base 2 can be found in O(log(word_size)) time, so as long as you are using integer indices with a fixed number of bits, this effectively constant.

See this question for information on fast ways to compute log base 2: Fast computing of log2 for 64-bit integers