Binary Search Tree using C++

// this program about binary search tree :
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int ele;
node *left;
node *right;
};
typedef struct node *nodeptr;
class stack
{
private:

struct snode
{
nodeptr ele;
snode *next;
};
snode *top;
public:

stack()
{
top=NULL;
}
void push(nodeptr p)
{
snode *temp;
temp = new snode;
temp-> ele = p;
temp->next = top;
top=temp;
}

void pop( )
{
if (top != NULL)
{
nodeptr t;
snode *temp;

temp = top;
top=temp->next;
delete temp;
}
}
nodeptr topele()

{

if (top !=NULL)
return top->ele;
else
return NULL;
}
int isempty()
{
return ((top == NULL) ? 1 : 0);
}
};
class bstree
{
public:
void insert(int,nodeptr &) ;
void del(int,nodeptr &) ;
int deletemin(nodeptr &) ;
void find(int,nodeptr &) ;
nodeptr findmin(nodeptr) ;
nodeptr findmax(nodeptr) ;
void copy(nodeptr &,nodeptr &);
void makeempty(nodeptr &) ;
nodeptr nodecopy(nodeptr &);
void preorder(nodeptr) ;
void inorder(nodeptr) ;
void postorder(nodeptr) ;
void preordernr(nodeptr) ;
void inordernr(nodeptr) ;
void postordernr(nodeptr) ;
void leftchild(int,nodeptr &);
void rightchild(int,nodeptr &);

};
void bstree :: insert(int x, nodeptr &p)
{
if (p==NULL)
{
p = new node;
p->ele=x;
p->left=NULL;
p->right=NULL;
}
else
{
if (x < p->ele)
insert(x,p->left);
else
if (x>p->ele)
insert(x,p->right);
else
cout<<"Element already Exits !"<<endl;
}

}
void bstree:: del(int x,nodeptr &p)
{
nodeptr d;
if (p==NULL)
cout<<"Element not found ";
else

if (x < p->ele)
del(x,p->left);
else
if (x > p->ele)
del(x,p->right);
else
if ((p->left == NULL) && (p->right ==NULL))
{

d=p;

p=NULL;
}
else
if (p->left == NULL)
{
d=p;
p=p->right;
}
else
if (p->right ==NULL)
{
d=p;
p=p->left;
}
else

p->ele=deletemin(p->right);

}
int bstree::deletemin(nodeptr &p)
{
int c;
if (p->left == NULL)
{
c=p->ele;
p=p->right;
return c;
}
else
c=deletemin(p->left);
return c;
}
void bstree::copy(nodeptr &p,nodeptr &p1)
{
makeempty(p1);
p1=nodecopy(p);
}
void bstree::makeempty(nodeptr &p)
{
nodeptr d;

if (p!=NULL)
{
makeempty(p->left);

makeempty(p->right);
d=p;
p=NULL;
}
}
nodeptr bstree::nodecopy(nodeptr &p)

{

nodeptr temp;
if (p == NULL)
return p;
else
{
temp = new node;
temp->ele=p->ele;
temp->left = nodecopy(p->left);
temp->right = nodecopy(p->right);
return temp;
}
}
nodeptr bstree::findmin(nodeptr p)
{
if (p==NULL)
{
cout<<"Tree is empty !";
return p;
}
else
{
while (p->left !=NULL)
p=p->left;
return p;
}
}
nodeptr bstree::findmax(nodeptr p)
{
if (p==NULL)
{
cout<<"Tree is empty !";
return p;
}
else
{
while (p->right !=NULL)
p=p->right;
return p;
}
}
void bstree::find(int x,nodeptr &p)
{
if (p==NULL)
cout<<"Element not found !";
else
{
if (x < p->ele)
find(x,p->left);
else
if ( x> p->ele)
find(x,p->right);
else
cout<<"Element Found !";
}
}
void bstree::preorder(nodeptr p)
{
if (p!=NULL)
{
cout<< p->ele<<"-->";
preorder(p->left);
preorder(p->right);
}
}
void bstree::inorder(nodeptr p)
{
if (p!=NULL)
{
inorder(p->left);
cout<< p->ele<<"-->";
inorder(p->right);
}
}

void bstree::postorder(nodeptr p)
{
if (p!=NULL)
{
postorder(p->left);
postorder(p->right);
cout<< p->ele<<"-->";
}
}
void bstree::preordernr(nodeptr p)
{
stack s;
while (1)
{
if (p != NULL)
{
cout<< p->ele<<"-->";
s.push(p);
p=p->left;
}
else
if (s.isempty())
{
cout<<"Stack is empty";
return;
}
else
{
nodeptr t;
t=s.topele();
p=t->right;
s.pop();
}
}
}
void bstree::inordernr(nodeptr p)
{
stack s;
while (1)
{
if (p != NULL)
{
s.push(p);
p=p->left;
}
else
{
if (s.isempty())
{
cout<<"Stack is empty";
return;
}
else
{
p=s.topele();
cout<< p->ele<<"-->";
}
s.pop();
p=p->right;
}
}
}
void bstree::postordernr(nodeptr p)
{
stack s;
while (1)
{
if (p != NULL)
{
s.push(p);
p=p->left;
}
else
{
if (s.isempty())
{
cout<<"Stack is empty";
return;
}
else
if (s.topele()->right == NULL)
{
p=s.topele();
s.pop();
cout<< p->ele<<"-->";
if (p==s.topele()->right)
{
cout<< s.topele()->ele<<"-->";
s.pop();
}
}
if (!s.isempty())
p=s.topele()->right;
else
p=NULL;
}
}
}
void bstree::leftchild(int q,nodeptr &p)
{
if (p==NULL)
cout<<"The node does not exists ";
else
if (q < p->ele )
leftchild(q,p->left);
else
if (q > p->ele)
leftchild(q,p->right);
else
if (q == p->ele)

{
if (p->left != NULL)
cout<<"Left child of "<< q<<"is "<< p->left->ele;
else
cout<<"No Left child !";
}
}
void bstree::rightchild(int q,nodeptr &p)
{
if (p==NULL)
cout<<"The node does not exists ";
else
if (q < p->ele )
rightchild(q,p->left);
else
if (q > p->ele)

rightchild(q,p->right);
else
if (q == p->ele)
{
if (p->right != NULL)
cout<<"Right child of "<< q<<"is "<< p->right->ele;
else
cout<<"No Right Child !";
}
}
int main()
{
system("color 3f");
int ch,x,leftele,rightele;
bstree bst;
char c='y';

nodeptr root,root1,min,max;
root=NULL;
root1=NULL;
do
{
cout<<"_____________________"<<endl;

cout<<"\n Binary Search Tree"<<endl;

cout<<"_____________________"<<endl ;

cout<<" 1.Insertion " <<endl;

cout<<" 2.Deletion " <<endl;

cout<<" 3.NodeCopy" <<endl;

cout<<" 4.Find " <<endl;

cout<<" 5.Findmax" <<endl;

cout<<" 6.Findmin" <<endl;

cout<<" 7.Preorder " <<endl;

cout<<" 8.Inorder " <<endl;

cout<<" 9.Postorder" <<endl;

cout<<" 10.Leftchild" <<endl;
cout<<" 11.Rightchild" <<endl;
cout<<" 12.Exit" <<endl;
cout<<"_____________________"<<endl;
cout<<" Enter your choice :";
cin>>ch;
switch(ch)
{
case 1:
cout<<"Enter the element to get inserted :=";
cin>>x;
bst.insert(x,root);
cout<<"\n\nInorder traversal is :";
bst.inorder(root);

break;
case 2:
cout<<"Enter the element to get deleted :";
cin>>x;
bst.del(x,root);
bst.inorder(root);
break;
case 3:
bst.copy(root,root1);
cout<<"The new tree is :";
bst.inorder(root1);
break;
case 4:
cout<<"Enter the element to be searched :";
cin>>x;
bst.find(x,root);
break;
case 5:
if (root == NULL)
cout<<"Tree is empty";
else
{
max=bst.findmax(root);
cout<<"Largest element is : "<< max->ele<< endl;
}
break;
case 6:
if (root == NULL)
cout<<"Tree is empty";
else
{
min=bst.findmin(root);
cout<<"Smallest element is : "<< min->ele<< endl;
}
break;
case 7:
if (root==NULL)
cout<<"Tree is empty";
else
{
bst.preordernr(root);
cout<<"Preorder traversal (Recursive) is :";
bst.preorder(root);
}
break;
case 8:
if (root==NULL)
cout<<"Tree is empty";
else
{
bst.inordernr(root);
cout<<"Inorder traversal (Recursive) is :";
bst.inorder(root);
}
break;
case 9:
if (root==NULL)
cout<<"Tree is empty";
else
{
bst.postordernr(root);
cout<<"Postorder traversal (Recursive) is :";
bst.postorder(root);
}
break;
case 10:
if (root==NULL)
cout<<"Tree is empty";
else
{
cout<<"Enter the node for which the left child is to be found :";
cin>>leftele;
bst.leftchild(leftele,root);
}
break;
case 11:
if (root==NULL)
cout<<"Tree is empty";
else
{
cout<<"Enter the node for which the Right child is to be found :";
cin>>rightele;
bst.rightchild(rightele,root);
}
break;
case 12:
return 0;
default:
cout <<"\n\n ERROR!!!"; //Exceptional cases and bugs if present
}
cout<<"\n\nContinue [y/n] ???"<<endl;
cin>>c;
}
while (c=='y' || c == 'Y');
return 0;
}