// Binary Search Tree Program

#include "iostream.h"
#include "conio.h"
#include "iomanip.h"
class bnode
{
public:
bnode *left;
bnode *right;
int data;
bnode(){}
bnode(int e)
{
left = NULL;
right = NULL;
data = e;
}

};
class bst
{
bnode *root;
public:
bst(){ root = NULL;}
int find(int);
int insert(int);
int remove(int);
void display(void);
void inorder(bnode*);

};

int bst::find(int ele)
{
bnode *p=root;
while(p)
{
if(p->data == ele) return 1;
else if(p->data < p =" p"> right;
else p = p -> left;
} return 0;
}
int bst::insert(int ele)
{
bnode *p = root;
bnode *q = new bnode(ele);
bnode *pp;
if(root)
{
while(p)
{
pp = p;
if(p -> data < p =" p"> right;
else if(p -> data > ele) p = p -> left;
else return 1;
}
if(pp -> data < ele)
pp -> right = q;
else pp -> left = q;
}
else root = q;

return 0;
}

int bst::remove(int ele){
bnode *p = root; bnode *pp = NULL;
while(p && p ->data != ele){
pp = p;
if(p -> data > ele) p = p -> left;
else p = p -> right;
}if(!p) return 1;
if(p -> left && p -> right) {
bnode *s = p -> left;
bnode *ps = p;
while(s -> right) {
ps = s; s = s -> right;
}bnode *q = new bnode(s->data);
q -> left = p -> left;
q -> right = p ->right;
if(pp == NULL) root = q;
else if(pp -> left == p)
pp -> left = q;
else pp -> right = q;
if(ps == p) pp = q;
else pp = ps;
p = s;
}bnode *c;
if(p -> left) c = p -> left;
else c = p ->right;
if( p == root) root = c;
else {
if(p == pp -> left)
pp -> left = c;
else
pp -> right = c;
} delete p; return 0; }


void bst::display(void)
{
inorder(root);
}
void bst::inorder(bnode* p)
{
if(p)
{
inorder(p -> left);
cout< data;
inorder(p -> right);
}

}

int menu(void)
{
cout<<"\n Binary Search Tree Menu \n";
cout<<"\n 1 -> insert\n 2 -> Delete \n 3 -> find ";
cout<<"\n 4 -> display \n 5 -> exit ";
cout<<"\n Enter your choice :";
int ch;
cin>>ch;
return ch;

}

void main()
{
bst b; int ch,ele;
do{
clrscr();
ch = menu();
switch(ch) {
case 1: cout<<"\n Enter the element to insert :";
cin>>ele;
if(b.insert(ele))
cout<<"\n Duplicate element ";
break;
case 2: cout<<"\n Enter the element to remove :";
cin>>ele;
if(b.remove(ele))
cout<<"\n Element not in the list:";
break;
case 3: cout<<"\n Enter the element to find:";
cin>>ele;
if(b.find(ele))
cout<<"\n Element found";
else
cout<<"\n Element not found :";
break;
case 4: cout<<"\n The elements in the list :";
b.display();
break;
case 5: break;
default:
cout<<"\n Invalid choice . Try again"; } getch(); }while(ch != 5);
}