Binary search tree using struct

//******************************************
//
///       BINARY SEARCH TREE USING STRUCTUR
//                                                     ucp junior    
//*********************************************      

           

#include<iostream>

#include<conio.h>
using namespace std;

struct node
{
int data;
node *right;
node *left;
};


void insert(int,node*&,int&);
bool Delete(int,node*&);
void InOrder(node*);
void PreOrder(node*);
void PostOrder(node*);
int successor(int,node*&);
int predecessor(node*,node*,int,int);
int height(node*);
node *root=nullptr;
node* pre=nullptr;



int main()
{
bool flag=false;
char option;
int num,ans,min=0;
bool result;

cout<<"\n\n\n";
cout<< "**********************************************\n";
cout<<   "!!!!!!+++++++++++++++++++++++++++++++++!!!!!!\n";
cout<< "           WELCOME TO OUR FINAL PROJECT\n";
cout<< "!!!!!!+++++++++++++++++++++++++++++++++!!!!!!\n";
cout<< "***********************************************\n";
//system("cls");
cout<<"\n\n\n";
cout<< "**********************************************\n";
cout<< "!!!!!!+++++++++++++++++++++++++++++++++!!!!!!\n";
cout << "           Binary Search Tree\n";
cout<< "!!!!!!+++++++++++++++++++++++++++++++++!!!!!!\n";
cout<< "***********************************************\n";
//system("cls");
while(!flag)
{
cout<<"\n\n\n";
cout<< "**********************************************\n";
cout<< "!!!!!!+++++++++++++++++++++++++++++++++!!!!!!\n";
cout << "                   MENU \n";
cout<< "!!!!!!+++++++++++++++++++++++++++++++++!!!!!!\n";
cout<< "***********************************************\n\n";
cout<<"1 : "<<"Press I/i for Insertion\n";
cout<<"2 : "<<"Press D/d for Deletion\n";
cout<<"3 : "<<"Press O/o To view Inordern\n";
cout<<"4 : "<<"Press R/r To view Pre-order\n";
cout<<"5 : "<<"Press V/v To view Post-order\n";
cout<<"6 : "<<"Press S/s To Find Successor\n";
cout<<"7 : "<<"Press P/p To Find Predecessor\n";
cout<<"8 : "<<"Press H/h For Height\n";
cout<<"9 : "<<"Press E/e To exit \n";
option=_getch();

switch(option)
{
case 'i':
case 'I':
{
cout<<"Enter Number To insert In BST : ";
cin>>num;
insert(num,root,min);
break;
}
case 'd':
case 'D':
cout<<"Enter Number To delete from BST : ";
cin>>num;
/*if(root==nullptr)
cout<<"\n\n\tTHERE ARE NO ELEMENTS IN BST\n";
else*/
result=Delete(num,root);
if(result==true)
cout<<num<<" IS DELETED FROM BST\n";
else
cout<<num<<" IS NOT FOUND IN THE BST\n";
break;
case 'o':
case 'O':
cout<<"\n\nINORDER : ";
InOrder(root);
break;
case 'r':
case 'R':
cout<<"\n\nPREORDER : ";
PreOrder(root);
break;
case 'v':
case 'V':
cout<<"\n\nPOSTORDER : ";
PostOrder(root);
break;
case 's':
case 'S':
cout<<"\nEnter The Number Of Which You Want The Successor : ";
cin>>num;
if(root==nullptr)
cout<<"\nThere are no Elements in the BST \n";
else
{
ans=successor(num,root);
if(ans==-1)
cout<<"NO SUCCESSOR\n";
else
cout<<"\nSUCCESSOR : "<<ans<<endl;
}
break;
case 'p':
case 'P':
{
min=root->data;
cout<<"\nEnter The Number Of Which You Want The Predecessor : ";
cin>>num;
if(root==nullptr)
cout<<"There are no Elements in the BST \n";
else
{
ans=predecessor(root,pre,num,min);
if(ans==-1)
cout<<"NO PREDECESSOR\n";
else
cout<<"\nPREDECESSOR : "<<ans<<endl;;
}
break;
}
case 'h':
case 'H':
ans=height(root);
cout<<"HEIGHT : "<<ans<<endl;
break;
case 'e':
case 'E':
exit(0);
default:
cout<<"\t\tINVALID ENTRY\n";
}
}
}


/*int main()
{
int num,size;
cout<<"HOW Many Numbers Do YOu Want In Your Tree : ";
cin>>size;
for(int i=0; i<size; i++)
{
cout<<"Enter Num : ";
cin>>num;
insert(num,root);
}
bool a;
for(int i=0; i<2 ;i++)
{
cout<<"ENTER NUM : ";
cin>>num;
a=Delete(num,root);
if(a==true)
cout<<num<<" IS DELETED\n";
else
cout<<"NUMBER NOT FOUND\n";
}
InOrder(root);
cout<<endl;
PreOrder(root);
cout<<endl;
PostOrder(root);
cout<<endl;
int ans;
ans=height(root);
cout<<"HEIGHT : "<<ans<<endl;
int min=root->data;
for(int i=0; i<size; i++)
{
cout<<"Enter Num : ";
cin>>num;
ans=predecessor(root,pre,num,min);
if(ans==-1)
cout<<"NO PREDECESSOR\n";
else
cout<<"PREDECESSOR : "<<ans<<endl;
/*if(ans==0)
cout<<"\nNO SUCCESSOR \n";
else
cout<<"\nSUCCESSOR : "<<ans<<endl;
}
min=root->data;
pre=nullptr;
for(int i=0; i<size; i++)
{
cout<<"Enter Num : ";
cin>>num;
ans=successor(num,root);

//if(ans==0)
// cout<<"\nNO SUCCESSOR \n";
//else
if(ans==-1)
cout<<"NO SUCCESSOR\n";
else
cout<<"\nSUCCESSOR : "<<ans<<endl;
}
}*/

void insert(int num,node*&root,int &min)
{
node *leaf;
node *temp=root;
node *temp1=nullptr;
if(temp==nullptr)
{
leaf=new node;
leaf->data=num;
leaf->right=nullptr;
leaf->left=nullptr;
root=leaf;
}
else if(temp->data==num)
cout<<"\n\nNUMBER ALREADY IN BINARY SEARCH TREE\n";
else
{
while(temp!=nullptr)
{
temp1=temp;
if(num>temp->data)
temp=temp->right;
else
temp=temp->left;
}
leaf=new node;
leaf->data=num;
leaf->right=nullptr;
leaf->left=nullptr;

if(num>temp1->data)
temp1->right=leaf;
else
temp1->left=leaf;
}
}

void InOrder(node *leaf)
{
//system("cls");
if(leaf!=nullptr)
{
InOrder(leaf->left);
cout<<leaf->data<<" ";
InOrder(leaf->right);
}
}

void PreOrder(node *leaf)
{
//system("cls");
if(leaf!=nullptr)
{
cout<<leaf->data<<" ";
PreOrder(leaf->left);
PreOrder(leaf->right);
}
}

void PostOrder(node *leaf)
{
// system("cls");
if(leaf!=nullptr)
{
PostOrder(leaf->left);
PostOrder(leaf->right);
cout<<leaf->data<<" ";
}
}

int successor(int num,node*&root)
{
node *temp=root,*temp1=nullptr;
int max=root->data,pre;
if(num==root->data)
{
if(temp->right==NULL)
return -1;
temp=temp->right;
while(temp->left!=NULL)
{
temp1=temp;
temp=temp->left;
}
return temp->data;
}
while(temp!=nullptr)
{
max=temp->data;
if(max!=num)
pre=max;
if(num<temp->data)
temp=temp->left;
else if(num>temp->data)
{
temp=temp->right;
if(temp->right==nullptr && num==temp->data)
{
return -1;
break;
}
}
else if(num==temp->data)
{
if(temp->data>root->data)
{
if(pre>root->data && num<pre)
return pre;
}
if(temp->right!=nullptr)
{
return(temp->right)->data;
}
else
{
if(pre<root->data && num<pre)
{
return pre;
}
else
return root->data;
break;
}
}
}
}

int predecessor(node *root,node *pre,int num,int min)
{
if(root!=nullptr)
{
if(min>root->data)
min=root->data;
if(min==num && root->left==NULL)
{
return -1;
}

else if(root->data==num)
{
if(root->left!=NULL)
{
node *temp=root->left;
while(temp->right)
temp=temp->right;
pre=temp;
return pre->data;
}
else
{
return pre->data;
}
}
else if(root->data < num)
{
pre=root;
predecessor(root->right,pre,num,min);

}
else
predecessor(root->left,pre,num,min);



}
}



int height(node *depth)
{
// system("cls");
int left=0,right=0;
if(depth==NULL)
return 0;
else
{
left=height(depth->left);
right=height(depth->right);
if(left>right || left==right)
return (left+1);
else
return (right+1);

}
}
bool Delete(int num,node*& root){
node *temp=root;
node *prev=nullptr;
node *child=nullptr;
node *childprev=nullptr;
bool ifroot=false; // to check if node is root(true) or not(false)

while(temp!=nullptr && temp->data!=num )
{
prev=temp;
if(num>temp->data)
temp=temp->right;
else
temp=temp->left;
}

if(temp==root)
ifroot=true;

if(temp==nullptr){
return false;
}

// if node is child
if(temp->right==nullptr && temp->left==nullptr)
{
if(ifroot)
{
root=nullptr;
delete root;
}
else
{
if(prev->left==temp)
prev->left=nullptr;
else
prev->right=nullptr;
delete temp;
}
return true;
}

// if node has only left subtree
if(temp->right==nullptr)
{
if(!ifroot)
{
if(temp->data < prev->data)
{
prev->left=temp->left;
if(prev->data==root->data)
root=prev;
}
else
{
prev->right=temp->left;
}
}
else
{
root=temp->left;
}
delete temp;
return true;
}

// if node has only right subtree
if(temp->left==nullptr)
{
if(!ifroot)
{
if(temp->data < prev->data)
{
prev->left=temp->right;
}
else
{
prev->right=temp->right;
}
}
else
{
root=temp->right;
}
delete temp;
return true;
}
// to delete any intermediate node
childprev=temp;
child=temp->right;

while(child->left!=nullptr)
{
childprev=child;
child=child->left;
}

temp->data=child->data;
childprev->right=child->right;
delete child;
return true;
}
///////////////////////////////////////////finish/////////////////////////////////////////////////////////////////////////