CODEWITHSUNDEEP
algorithmoptimizationtreebinary-tree
coder hacker
coder hacker

Reputation: 4868

Lowest Common Ancestor

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

Upvotes: 4

Views: 904

Answers (2)

Vikram Bhat
Vikram Bhat

Reputation: 6246

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 :-

  1. get bits needed to represent x & y which using binary search is O(log(32))
  2. the common prefix of binary notation of x & y is the common ancestor
  3. whichever is represented by larger no of bits is brought to same bit by k >> diff
  4. k = x^y erazes common prefix of x & y
  5. find bits representing the remaining suffix
  6. 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

Upvotes: 2

Vaughn Cato
Vaughn Cato

Reputation: 64308

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

Upvotes: 5

Related Questions