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).

Please clarify how the tree is represented: it sounds like it is stored in an array, where the children of the the node at index X are at indices 2*x and 2*x+1. — Scott Hunter, Apr 10 '14 at 14:12
its not necessary to store tree, as node are numbered sequentially and we can get child with 2*x and 2*x+1 — coder hacker, Apr 10 '14 at 14:15
So the nodes are numbered AS IF they were stored in an array. — Scott Hunter, Apr 10 '14 at 14:22

score 5 · Answer 1 · edited May 23 '17 at 12:03

5

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

Shift right the larger number until the leading 1 bit is in the same place as the other number.
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

edited May 23 '17 at 12:03

Community

1
1

answered Apr 10 '14 at 14:21

Vaughn Cato

63,448
5
82
132

I knew there was something like this; very nice. – Scott Hunter Apr 10 '14 at 14:23
This is still O(height of tree), not constant. Although it should be faster than traversing nodes. The only way it could be considered constant if there's some magic way to get log base 2 in a single machine instruction, without considering O(number of bits) operations. – user2566092 Apr 10 '14 at 14:27
@user2566092: Yes, maybe it is not technically in constant time, but log base 2 can be found in log(log(n)) time, and for any particular word size this is a constant. – Vaughn Cato Apr 10 '14 at 14:37
I was just about to add an answer explaining how to get integer log base2 in log(number of bits) operations. You might want to add that to your answer. – user2566092 Apr 10 '14 at 14:41
@VaughnCato Do we need to take difference of log of two numbers and shift the original number. Please clarify as that part is not very clear. – coder hacker Apr 10 '14 at 15:39
@TejasPatel: I've added some pseudocode to help explain the steps. See if that helps. – Vaughn Cato Apr 10 '14 at 16:49
@VaughnCato Yes the pseudo code greatly helps, thanks – coder hacker Apr 11 '14 at 02:50

Vikram Bhat · Accepted Answer · 2014-04-11T09:27:54.570

Edit :-

Faster way to get the common_ancestor in O(log(logn)) :-

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  

}

Explanation :-

get bits needed to represent x & y which using binary search is O(log(32))

the common prefix of binary notation of x & y is the common ancestor

whichever is represented by larger no of bits is brought to same bit by k >> diff

k = x^y erazes common prefix of x & y

find bits representing the remaining suffix

shift x or y by suffix bits to get common prefix which is the common ancestor.

Example :-

x = 12 = b1100 
y = 8  = b1000

xbits = 4
ybits = 4
diff = 0
k = x^y = 4 = b0100
kbits = 3
res = x >> kbits = x >> 3 = 1

ans : 1

I tried the same thing, but would take long if the root is common ancestor — coder hacker, Apr 11 '14 at 02:51
Yes the perfect approach, but the same solution is given in above question. Thanks, your explanation is much better so accepting your answer. — coder hacker, Apr 11 '14 at 09:23

Lowest Common Ancestor

2 Answers2