Tree: Find Lowest Common Ancestor

Problem: Given a binary search tree and 2 values find the lowest common ancestor.

Solution: Lets take a sample tree and see what finding the lowest ancestor means. The figure to the left shows the sample tree. To take an example, lets say the problem asked us to find the lowest common ancestor for nodes 10 and 14. Visually we can tell that node 12 is the lowest common ancestor. 15 is also a common ancestor but its not the lowest.

Since the tree is a binary search tree all the nodes to the right of any node within the tree have greater values that the node itself and all the nodes to the left have smaller values than the node. This property helps us in implementing the optimal solution to this problem. We start analyzing values at the root node and recursively arrive at a node where the two input values fall on different sides of the node. If they are on the same side of the node we recursively analyze the corresponding branch. For example, we start at 15 and see that 10 and 14 are both less than 15, so we choose the left branch and arrive at 12. Now, 10 is on the left of 12 and 14 is on the right. This is the node we are interested in. There is a non-recursive solution to this problem which basically uses the same idea, which I'll post soon.

Code:
Node * Find-Lowest-Common-Ancestor(Node *pRoot, int val1, int val2)
{
 if(pRoot == NULL) return NULL;

 // if both the values are less than the current node value
 // the common ancestor must be to the left
 if(val1 < pRoot->data && val2 < pRoot->data);
 {
    return Find-Lowest-Common-Ancestor(pRoot->left, val1, val2);
 }
 // if both the values are greater than the current node value
 // the common ancestor must be to the right
 else if(val1 > pRoot->data && val2 > pRoot->data)
 {
    return Find-Lowest-Common-Ancestor(pRoot->right, val1, val2);
 }
 else
 {
    return pRoot;
 }
}

13 comments:

  1. The above solution is only partially right, if the node for which we are finding Least Common Ancestor are in the same sub-tree but at different levels, the solution wont work...
    Eg: srch for 25 and 24 in the above image

    so here is my solution that can tackle both conditions:

    // let n1 and n2 be the nodes for which we need to find ancestor
    // find level of n1 and level of n2
    // find smaller of the levels and pass that to the below function
    // returns the pointer to the least common ancestor node

    NODE getLCA(NODE root,NODE n1,NODE n2,int level){
    if(root){
    level--;
    if(level){
    if(root's value is greater than the the value of n1 and n2) // go left
    return(getLCA(root->left,n1,n2,level));
    if(root's value is lesser than the the value of n1 and n2) // go right
    return(getLCA(root->right,n1,n2,level));
    //if n1 and n2 are in different subtrees
    if(root's value is lesser than one of the nodes(n1 or n2) and
    root's value is greater than one of the nodes(n1 or n2))
    return root;
    }
    return root;
    }

    this will do the job, if any updations\queries\bugs
    do let me kno....

    ReplyDelete
  2. When I was asking this question by an interviewer we had agreed upon the fact that in case of nodes that are in the same sub-tree but at different levels (ex. 25 and 24) the number closer to the root would server as its own ancestor. But, technically speaking you are right and the solution involving levels that you posted should work.

    ReplyDelete
  3. The 1st line should read:
    "When I was ASKED..."

    ReplyDelete
  4. hey..we can do this without introducing the level stuff and all.The iterative solution is:

    node* Findlowest(node *root, int v1,int v2)
    {
    node * current = root;
    while(1)
    if(current->value < v1 && current->value right==v1 || current->right == v2)
    return current;
    else
    current = current->right;
    }
    elseif(current->value >v1 && current->value >v2)
    {
    if(current->left == v1 || current->left == v2)
    return current;
    else
    current = current->left;
    }
    else
    return current;
    }
    }

    if we want to do it recurrsively then
    instead of changing current value , current = current->left, every time call the funtion like
    LCA( current->left, v1,v2)
    and that time no need to use while(1);

    ReplyDelete
  5. Find the comprehensive solution for the same problem in Java at
    http://technicalypto.blogspot.com/2010/02/find-common-parent-in-binary-search.html

    ReplyDelete
  6. Nice post!

    I have provided two solutions one the conventional one and the other without using the parent node to find the LCS. Both can be found here,
    http://www.technicalypto.com/2010/02/find-common-parent-in-binary-search.html

    http://www.technicalypto.com/2010/02/least-common-ancestor-without-using.html

    Hope you find it useful.

    ReplyDelete
  7. you can also use Range minimum query for the same and it would speed up solution for cases when you have a huge difference between the ranges you are looking at.

    ReplyDelete
  8. I would like to know what is the LCA for 24 & 25. Is it 25? Similarly if we choose 12 & 10, is the LCA is 12?

    ReplyDelete
  9. In case of 24 and 25 the interviewer had agreed to use 25 as Lowest Common Ancestor. But, it may depend on the interview.

    ReplyDelete
  10. I think this is wrong..... Lowest common Ancestor for 25 and 24 should NOT be 25 but 15. Because ofcourse 15 is lower than 25 and ancestor of both 25 and 24 So in the algo if both nodes are greater than current node (values) or one is less and one is greater then the current node should be the lowest ancestor. - Pawan

    ReplyDelete
  11. I am considering here lowest means lowest in value... so ofcourse 15 is lower than 23 by value.... please correct me if I am getting it wrong - Pawan

    ReplyDelete
  12. @pawan: lowest is not the numeric lowest. Lowest means lowest in the tree level. root node would be the highest level and leaf node is lowest level. It has nothing to do with the numbers contained in the nodes.

    ReplyDelete