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