How to find the lowest common ancestor of two node

Question

The Binary Tree here is may not necessarily be a Binary Search Tree.
The structure could be taken as -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

The maximum solution I could work out with a friend was something of this sort -
Consider this binary tree :

Binary Tree http://lcm.csa.iisc.ernet.in/dsa/img151.gif

The inorder traversal yields - 8, 4, 9, 2, 5, 1, 6, 3, 7

And the postorder traversal yields - 8, 9, 4, 5, 2, 6, 7, 3, 1

So for instance, if we want to find the common ancestor of nodes 8 and 5, then we make a list of all the nodes which are between 8 and 5 in the inorder tree traversal, which in this case happens to be [4, 9, 2]. Then we check which node in this list appears last in the postorder traversal, which is 2. Hence the common ancestor for 8 and 5 is 2.

The complexity for this algorithm, I believe is O(n) (O(n) for inorder/postorder traversals, the rest of the steps again being O(n) since they are nothing more than simple iterations in arrays). But there is a strong chance that this is wrong. :-)

But this is a very crude approach, and I'm not sure if it breaks down for some case. Is there any other (possibly more optimal) solution to this problem?

Answer 1

I have made an attempt with illustrative pictures and working code in Java,

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

Answer 2

This can be found at:- http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

Answer 3

Here is the working code in JAVA

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

Answer 4

If it is full binary tree with children of node x as 2*x and 2*x+1 than there is a faster way to do it

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;  
}

How does it work

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.

This works because basically divide the larger number by two recursively until both numbers are equal. That number is the common ancestor. Dividing is effectively the right shift opearation. So we need to find common prefix of two numbers to find the nearest ancestor

Answer 5

The below recursive algorithm will run in O(log N) for a balanced binary tree. If either of the nodes passed into the getLCA() function are the same as the root then the root will be the LCA and there will be no need to perform any recussrion.

Test cases. [1] Both nodes n1 & n2 are in the tree and reside on either side of their parent node. [2] Either node n1 or n2 is the root, the LCA is the root. [3] Only n1 or n2 is in the tree, LCA will be either the root node of the left subtree of the tree root, or the LCA will be the root node of the right subtree of the tree root.

[4] Neither n1 or n2 is in the tree, there is no LCA. [5] Both n1 and n2 are in a straight line next to each other, LCA will be either of n1 or n2 which ever is closes to the root of the tree.

//find the search node below root
bool findNode(node* root, node* search)
{
    //base case
    if(root == NULL)
        return false;

    if(root->val == search->val)
        return true;

    //search for the node in the left and right subtrees, if found in either return true
    return (findNode(root->left, search) || findNode(root->right, search));
}

//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
    //base case
    if(root == NULL)
        return NULL;

    //If 1 of the nodes is the root then the root is the LCA
    //no need to recurse.
    if(n1 == root || n2 == root)
        return root;

    //check on which side of the root n1 and n2 reside
    bool n1OnLeft = findNode(root->left, n1);
    bool n2OnLeft = findNode(root->left, n2);

    //n1 & n2 are on different sides of the root, so root is the LCA
    if(n1OnLeft != n2OnLeft)
        return root;

    //if both n1 & n2 are on the left of the root traverse left sub tree only
    //to find the node where n1 & n2 diverge otherwise traverse right subtree
    if(n1OnLeft)
        return getLCA(root->left, n1, n2);
    else
        return getLCA(root->right, n1, n2);
}

Answer 6

Try like this

node * lca(node * root, int v1,int v2)
{

if(!root) {
            return NULL;
    }
    if(root->data == v1 || root->data == v2) {
        return root;}
    else
    {
        if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data))
        {
            return root;
        }

        if(v1 < root->data && v2 < root->data)
        {
            root = lca(root->left, v1, v2);
        }

        if(v1 > root->data && v2 > root->data)
        {
            root = lca(root->right, v1, v2);
        }
    }
return root;
}