Lowest common ancestor of binary search tree

Question : Write a function to print the lowest common ancestor of two nodes in a binary search tree. 

Lowest common ancestor of two nodes x and y in a binary tree is the lowest node that has both x and y as descendants.

Here lowest common ancestor of 1 and 7 is 3. LCA of 13 and 7 is root - 8. And LCA of 6 and 7 is 6 itself.

The program to find gets complicated for an ordinary binary tree. But for a binary search tree, it is quite simple.

As we see from the diagram above, the paths to 1 and 4 are common till the node 3. And at 3 they branch in different directions. So 3 is our LCA.

That is lowest common ancestor is the node where the paths to x and y from root deviate. As long as they branch in same direction, we continue to traverse. When they branch in different directions, that is the lowest common ancestor.

So let us write a simple algorithm,

1. set temp=root
2. if temp->val >x and temp->val>y
1. temp = temp->left
3. else if temp->val<x and temp->val <y
1. temp = temp->right
4. if neither then  break the loop and we have found our LCA
5. repeat steps 2 to 6 until temp is null

Here is the function for finding lowest common ancestor in C.

NODEPTR lowest_common_ancestor(NODEPTR root, int num1,int num2)
{
   NODEPTR temp = root;
   while(temp!=NULL)
   {
        if(num1>temp->val && num2>temp->val ) 
              temp = temp->right; 
        else if(num1<temp->val && num2<temp->val)
              temp= temp->left;
        else
              break; 
    }
    return temp;  
}

Here is the driver program

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d---",nd->val);
        in_order(nd->right);
     }
}
NODEPTR lowest_common_ancestor(NODEPTR root, int num1,int num2)
{
   NODEPTR temp = root;
   while(temp!=NULL)
   {
        if(num1>temp->val && num2>temp->val ) 
              temp = temp->right; 
        else if(num1<temp->val && num2<temp->val)
              temp= temp->left;
        else
              break; 
    }
    return temp;  
} 


int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
       
       printf("\nInorder traversal\n");
       in_order(root);
      
       while(1)
       {
          NODEPTR snode;
          int num1,num2;
          printf("Enter two values num1 and num2:");
          scanf("%d %d",&num1,&num2);
          snode = lowest_common_ancestor(root,num1,num2);
          if(snode==NULL)
             printf("Value not found");
          else 
             printf("ancestor is %d\n",snode->val);
       }
       return 0;
}