Binary Search Tree with all Operations

#include "stdafx.h"
#include<iostream>
#include<conio.h>>
using namespace std;
int flag=0;
struct Node
{
int data;
Node *left;
Node *right;
};
class BST
{
private:
int check1;
int check2;
public:
Node *root;
BST()
{
root=NULL;
check1=0;
check2=1;
}
void find_parent(int data,int &found,Node* &parent)
{
Node *ptr;
found=check1;
parent=NULL;
ptr=root;
while(ptr!=NULL)
{
if(ptr->data==data)
{
found=check2;
}
if(ptr->data>data)
{
parent=ptr;
ptr=ptr->left;
}
else
{
parent=ptr;
ptr=ptr->right;
}
}
}
void insert_values(int data)
{
int found;
Node *temp,*parent;
find_parent(data,found,parent);
if(found==check2)
{
cout<<"\nData with such value already exists\n";
}
else
{
temp=new Node;
temp->data=data;
temp->left=NULL;
temp->right=NULL;
if(parent==NULL)
{
root=temp;
}
else if(parent->data>data)
{
parent->left=temp;
}
else
{
parent->right=temp;
}
}
}

void in_fix(Node *ptr)
{
if(ptr!=NULL)
{
in_fix(ptr->left);
cout<<ptr->data<<"\t";
   in_fix(ptr->right);
}
}
void post_fix(Node *ptr,int flag)
{
flag++;
if(ptr!=NULL)
{
post_fix(ptr->left,flag);
   post_fix(ptr->right,flag);
cout<<"\n\n\t\tData : Level\n";
cout<<"\n\t\t"<<ptr->data<<" : "<<flag<<endl;
}
}
void pre_fix(Node *ptr)
{
if(ptr!=NULL)
{
cout<<ptr->data<<"\t";
pre_fix(ptr->left);
   pre_fix(ptr->right);
}
}
void traverse_BST()
{
int choice;
cout<<"\n1)In-fix\n2)Pre-fix\n3)Post_fix\n\n\t\tWhat is your chice???\n";
cin>>choice;
if(choice==1)
{
in_fix(root);
}
else if(choice==2)
{
pre_fix(root);
}
else
{
post_fix(root,flag);
}
}
bool search_node(int search,Node *ptr )
{
if (root==NULL)
{
return false;
}
else if (search<ptr->data)
{
return search_node(search,ptr->left);
}
else if (search>ptr->data)
{
return search_node(search,root->right );
        }
else
{
return true;
}
}
int get_smallest(Node *ptr)
{
if (ptr->left==NULL)
{
return ptr->data;
}
else
{
return get_smallest(ptr->left);
}
}
int get_highest(Node *ptr)
{
if (ptr->right==NULL)
{
return ptr->data;
}
else
{
return get_highest(ptr->right);
}
}
void get_degree(Node *temp,int data)
{
int counter=0;
if(temp->data==data)
{
if(temp->left!=NULL)
{
counter++;
}
if(temp->right!=NULL)
{
counter++;
}
cout<<counter<<endl;
}
if(temp->left!=NULL)
{
get_degree(temp->left,data);
}
if(temp->right!=NULL)
{
get_degree(temp->right,data);
}
}
void recur_delete(int d,int &found,Node *&parent,Node *&x)
{
Node *ptr;
found=0;
if(root==NULL)
return;
ptr=root;
while(ptr!=NULL)
{
if(ptr->data==d)
{
found=1;
x=ptr;
return;
}
if(ptr->data>d)
{
parent=ptr;
ptr=ptr->left;
}
else
{
parent=ptr;
ptr=ptr->right;
}
}
}
void delete_node(int value)
{
Node *parent,*curr,*next;
int found;
if(root==NULL)
{
cout<<"\nBST is Empty!!!\n";
return;
}
parent=curr=NULL;
recur_delete(value,found,parent,curr);
if(found==0)
{
cout<<"\nNode with such value is not present!!!\n";
return;
}
if(curr->left!=NULL && curr->right!=NULL)
{
parent=curr;
next=curr->right;
while(next!=NULL)
{
parent=curr;
next=next->left;
}
curr->data=next->data;
curr=next;
}
if(curr->left==NULL && curr->right==NULL)
{
if(parent->right==curr)
{
parent->right=NULL;
}
else
{
parent->left=NULL;
}
delete curr;
return;
}
if(curr->left==NULL && curr->right!=NULL)
{
if(parent->left==curr)
{
parent->left=curr->right;
}
else
{
parent->right=curr->right;
}
delete curr;
return;
}
if(curr->left!=NULL && curr->right==NULL)
{
if(parent->left==curr)
{
parent->left=curr->left;
}
else
{
parent->right=curr->left;
}
delete curr;
return;
}
}
void show_min()
{
cout<<"\n\nMinum Value : "<<get_smallest(root);
}
void show_max()
{
cout<<"\n\nMaximum Value : "<<get_highest(root);
}
void search_result()
{
int search;
cout<<"\nEnter an Integer to Search : ";
cin>>search;
if(search_node(search,root)==true)
{
cout<<"\n"<<search<<" is present in BST!!!\n";
}
else
{
cout<<"\n"<<search<<" is not present in BST!!!\n";
}
}
void show_degree()
{
int data;
cout<<"Enter a value to find its degree :\n";
cin>>data;
cout<<"\nDegree of "<<data<<" is ";
get_degree(root,data);
}
BST(BST &s1)
{
root=new Node;
root->left=NULL;
root->right=NULL;
root->data=s1.root->data;
copy(root,s1.root);
}
void copy(Node *temp,Node *ptr)
{
if(ptr->left!=NULL)
{
temp->left=new Node;
temp->left->data=ptr->left->data;
temp->left->left=temp->left->right=NULL;
}
if(ptr->right!=NULL)
{
temp->right=new Node;
temp->right->data=ptr->right->data;
temp->right->left=temp->right->right=NULL;
}
if(ptr->left!=NULL)
{
copy(temp->left,ptr->left);
}
if(ptr->right!=NULL)
{
copy(temp->right,ptr->right);
}
}
};
int main()
{
BST s1;
int choice;
do
{
cout<<"\n\n\t\t\t-----Main Menu-----\n";
cout<<"\n1)Add New\n2)Traverse\n3)Get Degree\n4)Get Level \n5)Search a Node\n6)Get Minimum \n7)Get Maximum\n8)Delete\n9)Copy Constructor\n10)Quit\n";
cout<<"\n\t\t\tPlease select your choice : (1-10)\n";
cin>>choice;
if(choice==1)
{
int value;
       char choice;
cout<<"\nEnter data :";
            cin>>value;
            s1.insert_values(value);
do
{
cout<<"\nDo you want more ??? (y/n)\n";
cin>>choice;
if(choice=='y')
{
cout<<"\nEnter data :";
           cin>>value;
           s1.insert_values(value);
}
}
while(choice!='n');
}
else if(choice==2)
{
s1.traverse_BST();
}
else if(choice==3)
{
s1.show_degree();
}
else if(choice==5)
{
s1.search_result();
}
else if(choice==6)
{
s1.show_min();
}
else if(choice==7)
{
s1.show_max();
}
else if(choice==8)
{
int value;
cout<<"\nEnter a value to delete : ";
cin>>value;
s1.delete_node(value);
s1.traverse_BST();
}
else if(choice==9)
{
BST s2=s1;
cout<<"Entered data is \n";
s2.pre_fix(s2.root);
}
else if(choice==10)
{
//exit(0);
}
else
{
cout<<"\n\nInvalid Choice!!!Try again...\n";
}
}
while(choice!=10);
return 0;
}