```
// Program to implement Binary Search Tree operations
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node * root, *curr, *parent;
int dir;
public:
BinarySearchTree()
{
root = NULL;
}
int isEmpty()
{
if(root==NULL)
return 1;
else
return 0;
}
void print_inorder();
void inorder(tree_node*);
void insert(int);
void remove(int);
int search(int);
};
int BinarySearchTree::search(int d)
{
curr = root;
while(curr != NULL)
{
if(curr->data == d)
return 1;
else
{
parent = curr;
if(d>curr->data)
{
curr = curr->right;
dir=2;
}
else
{
curr = curr->left;
dir=1;
}
}
}
return 0;
}
// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data)
curr = curr->right;
else
curr = curr->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
void BinarySearchTree::remove(int d)
{
if(search(d))
{
tree_node *q,*pred,*succ;
if(root->data==d)
{
parent=NULL;
curr=root;
}
if(curr->left==NULL && curr->right==NULL)
q=NULL;
else if(curr->left==NULL && curr->right!=NULL)
q=curr->right;
else if(curr->left!=NULL && curr->right==NULL)
q=curr->left;
else
{
q=curr->right;
if(q->left==NULL)
q->left=curr->left;
else
{
pred=q;
succ=q->left;
while(succ->left!=NULL)
{
pred=succ;
succ=succ->left;
}
pred->left=succ->right;
q=succ;
q->left=curr->left;
q->right=curr->right;
}
}
if(parent==NULL)
root=q;
else if(dir==1)
parent->left=q;
else
parent->right=q;
cout<<" After Removal tree is: "<<endl;
print_inorder();
}
else
cout<<"\nElement not found";
}
void BinarySearchTree::print_inorder()
{
if(root)
inorder(root);
else
cout<<"\nTree empty";
}
void BinarySearchTree::inorder(tree_node* p)
{
if(p)
{
inorder(p->left);
cout<<" "<<p->data<<" ";
inorder(p->right);
}
}
void main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
clrscr();
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. Removal "<<endl;
cout<<" 3. Search "<<endl;
cout<<" 4. Exit "<<endl;
cout<<" \nEnter your choice : ";
cin>>ch;
switch(ch)
{
case 1 :
cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.insert(tmp);
cout<<" After Insertion tree is: ";
b.print_inorder();
break;
case 2 :
if(b.isEmpty())
cout<<"Tree empty";
else
{
cout<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
}
break;
case 3 :
if(b.isEmpty())
cout<<"\nTree Empty";
else
{
cout<<"\nEnter data to search :";
cin>>tmp1;
if(b.search(tmp1))
cout<<"\nElement found";
else
cout<<"\nElement not found";
}
break;
case 4:
exit(0);
}
}
}
```