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