C++ program to find lowest Common Ancestor in a binary search tree














































C++ program to find lowest Common Ancestor in a binary search tree



#include <iostream> 
#include <stdlib.h>
using namespace std;

/*
Description:
1.Create methods to implement binary search tree and insert elements.

2.Recursively finding the lowest common ancestor of two nodes in bst 
  so that one of the key is present in left subtree and other on the 
  right subtree, if any such node is present it is lowest common 
  ancestor. 
3.The recursive method lca follows the step 2 in such a manner that lca
  of two nodes is identified for the current node the it returns.
*/


class BinarySearchTree
{
public:
    struct TreeNode
    {
        int key; 
        TreeNode* left;
        TreeNode* right; 
    };
    TreeNode* root;
    TreeNode* curr1;
    TreeNode* curr2; 

public:
struct TreeNode *newNode(int item) 
    struct TreeNode *temp =  (struct TreeNode *)malloc(sizeof(struct TreeNode)); 
    temp->key = item; 
    temp->left = temp->right = NULL; 
    return temp;
}
struct TreeNode* insert(struct TreeNode* node, int key) 
    if (node == NULL) 
      return newNode(key); 
   
    if (key < node->key) 
        node->left  = insert(node->left, key); 
    else if (key > node->key) 
        node->right = insert(node->right, key);    
   
  return node; 
}

TreeNode* lca(TreeNode* root,int x ,int y)
{
  if(root==NULL)
  {
    return NULL;
  }
  if(root->key > max(x,y))
  {
    return lca(root->left,x,y);
  }
  if(root->key < min(x,y))
  {
    return lca(root->right,x,y);
  }
  return root;
}
};

int main() 
{  
  int as=1;
  do{
cout<<"\n1.CREATE A TREE\n"; 
  cout<<"2.TO FIND THE LOWEST COMMON ANCESTOR OF TWO ELEMENTS.\n";
cout<<"3.EXIT.\n";
int x;
int n,i=0,val;
BinarySearchTree t;
cout<<"\nENTER YOUR CHOICE:";
cin>>x;
switch(x)
{
case 1:
cout<<"\nENTER THE NUMBER OF ELEMENTS YOU WANT TO INSERT:";
t.root = NULL; 
cin>>n;
cout<<"\nENTER "<<n<<" ELEMENTS:";
while(i!=n)
{
  cin>>val;
  if(i==0)
  {
  t.root = t.insert(t.root,val); 
  }
    t.insert(t.root,val);
  i++;
}
break;
    case 2:
      cout<<"\nENTER THE TWO ELEMENTS :";
      int x,y;
      cin>>x>>y;
      cout<<"\n"<<(t.lca(t.root,x,y))->key<<" is the lowest common ancestor element";
      break;  
case 3:
  as=0;
     break;
}
}while(as);
return 0; 

/*
OUTPUT :


1.CREATE A TREE
2.TO FIND THE LOWEST COMMON ANCESTOR OF TWO ELEMENTS.
3.EXIT.

ENTER YOUR CHOICE:1

ENTER THE NUMBER OF ELEMENTS YOU WANT TO INSERT:11

ENTER 11 ELEMENTS:15 10 25 8 12 20 30 6 9 18 22

1.CREATE A TREE
2.TO FIND THE LOWEST COMMON ANCESTOR OF TWO ELEMENTS.
3.EXIT.

ENTER YOUR CHOICE:2

ENTER THE TWO ELEMENTS :6 12

10 is the lowest common ancestor element
1.CREATE A TREE
2.TO FIND THE LOWEST COMMON ANCESTOR OF TWO ELEMENTS.
3.EXIT.

ENTER YOUR CHOICE:2

ENTER THE TWO ELEMENTS :10 12

10 is the lowest common ancestor element
1.CREATE A TREE
2.TO FIND THE LOWEST COMMON ANCESTOR OF TWO ELEMENTS.
3.EXIT.

ENTER YOUR CHOICE:2

ENTER THE TWO ELEMENTS :20 6

15 is the lowest common ancestor element
1.CREATE A TREE
2.TO FIND THE LOWEST COMMON ANCESTOR OF TWO ELEMENTS.
3.EXIT.

ENTER YOUR CHOICE:2

ENTER THE TWO ELEMENTS :18 22

20 is the lowest common ancestor element
1.CREATE A TREE
2.TO FIND THE LOWEST COMMON ANCESTOR OF TWO ELEMENTS.
3.EXIT.

ENTER YOUR CHOICE:2

ENTER THE TWO ELEMENTS :30 30 

30 is the lowest common ancestor element
1.CREATE A TREE
2.TO FIND THE LOWEST COMMON ANCESTOR OF TWO ELEMENTS.
3.EXIT.

ENTER YOUR CHOICE:3

*/

Comments