complete c++ implementation of Binary search tree with menu

BST_IMPLEMENT.h:

//ARSLAAN MUHAMMAD ALI
// ASSIGNMENT 5
// DATA STRUCTURES
// SECTION A


#include<iostream>
#include<cmath>
#include<math.h>
#include<iomanip>
#include<windows.h>
#include<queue>  //to be used in level order traversal
template<class D_type>

struct node
{   

D_type element;
node<D_type>* side_left;
node<D_type>* side_right;
};

template<class D_type>
class BST_IMPLEMENT
{
private:
node<D_type>* root;
void rec_cpy(node<D_type>* &copied_into,node<D_type>* copied_from)
{
if(copied_from==NULL)
{

copied_into=NULL;
}
else
{

copied_into=new node<D_type>;
copied_into->element=copied_from->element;
rec_cpy(copied_into->side_left,copied_from->side_left);
rec_cpy(copied_into->side_right,copied_from->side_right);

}
}
void rec_dele(node<D_type>* & root_pointer)
{
if(root_pointer!=NULL)
{

rec_dele(root_pointer->side_left);
rec_dele(root_pointer->side_right);
delete root_pointer;
root_pointer=NULL;
}
}
bool recursive_equality(node<D_type>* root_node_1,node<D_type>* root_node_2)
{
if(root_node_1==NULL && root_node_2==NULL)        
{
return true;
}

return(root_node_1 && root_node_2    &&  (root_node_1->element && root_node_2->element)  && recursive_equality(root_node_1->side_left,root_node_2->side_left) && recursive_equality(root_node_1->side_right,root_node_2->side_right));
}

int recursive_depth(node<D_type>* root_node)
{
if(root_node==NULL)
{
return 0;
}
else
{
return 1+max_of_2(recursive_depth(root_node->side_left),recursive_depth(root_node->side_right));
}
}

int recursive_count_nodes(node<D_type>* root_pointer)
{
int count=0;
if(root_pointer)
{
count++;
count=count+recursive_count_nodes(root_pointer->side_left);
count=count+recursive_count_nodes(root_pointer->side_right);

}
return count;
}

void recursive_mirror(node<D_type>* root_pointer)
{
if(root_pointer==NULL)
{
return;
}
process_node(root_pointer);
recursive_mirror(root_pointer->side_left);
recursive_mirror(root_pointer->side_right);
}

void  process_node(node<D_type>* root_pointer)
{
if(root_pointer==NULL)
{
return;
}
node<D_type>* temp;
temp=root_pointer->side_left;
root_pointer->side_left=root_pointer->side_right;
root_pointer->side_right=temp;
}

int max_of_2(int num1,int num2)
{
if(num1>=num2)
{
return num1;
}
else
{
return num2;
}
}

void delete_private(node<D_type>* & node_pointer)
{
node<D_type>* current;
node<D_type>* current_previous;
node<D_type>* temp;
if(node_pointer==NULL)
{
cout<<"The node to be deleted is NULL !"<<endl;
}
else if(node_pointer->side_left==NULL && node_pointer->side_right==NULL)
{
temp=node_pointer;
node_pointer=NULL;
delete temp;
}
else if(node_pointer->side_left==NULL)
{
temp=node_pointer;
node_pointer=temp->side_right;
delete temp;
}
else if(node_pointer->side_right==NULL)
{
temp==node_pointer;
node_pointer=temp->side_left;
delete temp;
}
else
{
current=node_pointer->side_left;
current_previous=NULL;
while (current->side_right!=NULL)
{
current_previous=current;
current=current->side_right;
}
node_pointer->element=current->element;
if(current_previous==NULL)
{
node_pointer->side_left=current->side_left;
}
else 

{
current_previous->side_right=current->side_left;
}
delete current;
}
}

void in_order(node<D_type>* node_pointer)
{
if(node_pointer!=NULL)
{
in_order(node_pointer->side_left);
cout<<node_pointer->element<<" ";
in_order(node_pointer->side_right);
}
}

void pre_order(node<D_type>* node_pointer)
{
if(node_pointer!=NULL)
{
cout<<node_pointer->element<<" ";
pre_order(node_pointer->side_left);
pre_order(node_pointer->side_right);
}
}

void post_order(node<D_type>* node_pointer)
{
if(node_pointer!=NULL)
{
post_order(node_pointer->side_left);
post_order(node_pointer->side_right);
cout<<node_pointer->element<<" ";
}
}

void level_by_level_traversal(node<D_type>* node_pointer)
{
if(node_pointer==NULL) 
return;
queue<node<D_type>*> Q;
Q.push(root);
while(!Q.empty())
{
node<D_type>* current=Q.front();
cout<<current->element<<" ";
if(current->side_left!=NULL)
{
Q.push(current->side_left);

}
if(current->side_right!=NULL)
{
Q.push(current->side_right);
}
Q.pop();
}
}

void print_skew(node<D_type>* node_pointer)
{

if (node_pointer->side_left!=NULL)
print_skew(node_pointer->side_left);
cout<<node_pointer->element<<" ";
if (node_pointer->side_right!=NULL)
print_skew(node_pointer->side_right);

}

void temp_recursive_inorder(node<D_type>* root_pointer)
{
if(root_pointer!=NULL)
{
temp_recursive_inorder(root_pointer->side_left);
cout<<root_pointer->element<<" ";
temp_recursive_inorder(root_pointer->side_right);
}
}

public:

//constructor and destructor and is_empty function
BST_IMPLEMENT()//constructor
{
root=NULL;
}                 

~BST_IMPLEMENT()//destructor

{
rec_dele(root);
}                 
bool is_empty()
{
return (root==NULL);
}

//general functions of tree
bool search(const D_type & key)
{
node<D_type>* current;
bool found=false;
if(root==NULL)
{
cout<<"The tree is empty and it cannot be searched !"<<endl;
}
else
{
current=root;
while(current!=NULL && !found)
{
if(current->element==key)
{
found=true;
}
else if(current->element>key)
{
current=current->side_left;
}
else
{
current=current->side_right;
}
}
}
return found;
}

void insert_item(const D_type & new_element)
{
node<D_type>* new_node;
node<D_type>* current;
node<D_type>* current_previous;

new_node=new node<D_type>;
new_node->element=new_element;
new_node->side_left=NULL;
new_node->side_right=NULL;

if(root==NULL)
{
root=new_node;
}
else 
{
current=root;
while(current!=NULL)
{
current_previous=current;
if(current->element==new_element)
{
cout<<"Duplicates not allowed !"<<endl;
return;
}
else if(current->element>new_element)
{
current=current->side_left;
}
else 
{
current=current->side_right;
}
}
if(current_previous->element>new_element)
{
current_previous->side_left=new_node;
}
else 
{
current_previous->side_right=new_node;
}
}
}

void delete_item(const D_type & delete_element)
{
node<D_type>* current;
node<D_type>* current_previous;
bool found=false;
if(root==NULL)
{
cout<<"Cannot delete from an empty tree !"<<endl;
}
else
{
current=root;
current_previous=root;
while (current!=NULL && !found)
{
if(current->element==delete_element)
{
found=true;
}
else
{
current_previous=current;
if(current->element>delete_element)
{
current=current->side_left;
}
else 
{
current=current->side_right;
}
}

}
if(current==NULL)
{
cout<<"The item to be deleted is not in the tree !"<<endl;

}
else if(found)
{
if(current==root)
{
delete_private(root);
}
else if(current_previous->element>delete_element)
{
delete_private(current_previous->side_left);
}
else 
{
delete_private(current_previous->side_right);
}
}
else 
{
cout<<"The element to be deleted is not in the tree !"<<endl;
}
}
}

void print()
{
int choice=0;
cout<<"Enter the choice !"<<endl;
cout<<"Enter 1 for inorder printing of tree !"<<endl;
cout<<"Enter 2 for preorder printing of tree !"<<endl;
cout<<"Enter 3 for postorder printing of tree !"<<endl;
cout<<"Enter 4 for level by level printing of tree!"<<endl;
cout<<"Enter 5 for Skewed printing of tree!"<<endl;
cin>>choice;
cout<<endl;
cout<<endl;
if(choice==1)
{
cout<<"The tree is "<<endl;
in_order(root);
}
else if(choice==2)
{
cout<<"The tree is "<<endl;

pre_order(root);
}
else if(choice==3)
{
cout<<"The tree is "<<endl;

post_order(root);
}
else if(choice==4)
{
cout<<"The tree is "<<endl;

level_by_level_traversal(root);
}
else if(choice==5)
{

cout<<"The Skewed Tree is \n";
print_skew(root);
}
}


//operator= and copy constructor for deep copy of tree
const BST_IMPLEMENT<D_type> & operator=(const BST_IMPLEMENT<D_type> & rightobject)
{
if(this!=&rightobject)
{
if(root!=NULL)
{
rec_dele(root);
}
if(rightobject.root==NULL)
{
root=NULL;
}
else
{
rec_cpy(root,rightobject.root);
}
}
return *this;
}

BST_IMPLEMENT(const BST_IMPLEMENT<D_type> & rightobject)
{
if(rightobject.root==NULL)
{
root=NULL;
}
else
rec_cpy(root,rightobject.root);

}

//operator== and count_nodes and heigth or depth of tree and mirror binary tree function
bool operator==(const BST_IMPLEMENT<D_type> & rightobject)
{
return recursive_equality(root,rightobject.root);

}

int count_nodes()
{
int count=0;
count=recursive_count_nodes(root);
return count;
}

int depth()
{
return recursive_depth(root);
}

void mirror_bst()
{
recursive_mirror(root);
}

void temp_inorder_traversal()
{
temp_recursive_inorder(root);
}


int getWidth(int k)
{
if(k>depth()) {
std::cout << "k is larger than the height of the tree\n";
return -1;
}

return DoGetWidth(root, k);
}

int DoGetWidth(node<D_type>* p, int k) 
{
if(p==NULL) 
return 0;

if(k==1)  
return 1;

return ( DoGetWidth(p->side_left, k-1) + 
DoGetWidth(p->side_right,k-1) ) ;
}



void printAllPath()
{
int height = depth();
int *path=new int[height];           // variable-length array

DoPrintAllPath(root,path, 0);
}

void DoPrintAllPath(node<D_type>* p, int *path, int pathLen)
{
if(p==NULL) return;

path[pathLen]=p->element;
pathLen++;

if (p->side_left==NULL && p->side_right==NULL) {
printPath(path, pathLen);
} else {
DoPrintAllPath(p->side_left, path, pathLen);
DoPrintAllPath(p->side_right,path, pathLen);
}
}

void printPath(int *path, int len)
{
for(int i=0; i<len; i++) {
std::cout << path[i] << " ";
}
std::cout << "\n";
}


};

driver run:

//ARSLAAN MUHAMMAD ALI
// ASSIGNMENT 5
// DATA STRUCTURES
// SECTION A


#include<iostream>
#include<windows.h>
#include"BST_IMPLEMENT.h"   //implementation of the tree is in the BST_IMPLEMENT.h file
using namespace std;

void take_Action()
{
cout<<endl;
cout<<endl;
cout<<"       Enter ONLY the number which is asked to be entered !"<<endl;
cout<<"       Enter 1 to delete an element from the TREE !"<<endl;
cout<<"       Enter 2 to search an element from the TREE !"<<endl;
cout<<"       Enter 3 to print the TREE !"<<endl;
cout<<"       Enter 4 to know the no of nodes in the Tree !"<<endl;
cout<<"       Enter 5 to know the Heigth/Depth of the TREE !"<<endl;
cout<<"       Enter 6 to check the equality of 2 Trees !"<<endl;
cout<<"       Enter 7 to mirror the binary search tree !"<<endl;
cout<<"       Enter 8 to know the Width Of the Tree !"<<endl;
cout<<"       Enter 9 to Print PathSum Of Binary Search Tree !"<<endl;
cout<<"       NOTE: ENTER -1 TO EXIT FROM THE BST_ASSIGNMENT#5 MENU !"<<endl;
}


void main()
{
HANDLE hconsole=0;
hconsole=GetStdHandle(STD_OUTPUT_HANDLE);

cout<<endl;
int data_type=0;
SetConsoleTextAttribute(hconsole,12);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet
cout<<"____________________________ BST ASSIGNMENT#5 _____________________________"<<endl;
cout<<endl;
cout<<endl;

SetConsoleTextAttribute(hconsole,13);
cout<<"---------------------PLEASE PROCEED FROM THE MENU--------------"<<endl;
cout<<endl;
cout<<endl;

cout<<"Enter the DATA_TYPE of element for Tree !"<<endl;
cout<<"Enter 1 for integer DATA_TYPE !"<<endl;
cout<<"Enter 2 for char DATA_TYPE !"<<endl;
cin>>data_type;

BST_IMPLEMENT<char>tree_1;
BST_IMPLEMENT<int>tree;

int menu=0;
cout<<endl;
cout<<endl;

int reqrd=0;
int temp=0;
char temp1=0;

int reqrd_for_tree_2=0;
int reqrd_for_tree_3=0;
int temp_for_tree_2=0;
char temp_for_tree_3=0;


SetConsoleTextAttribute(hconsole,6);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet


if(data_type==1)
{
cout<<"How many integers you want to insert ?"<<endl;
cin>>reqrd;
cout<<"Start entering the elements you want to insert into the tree !"<<endl;

for(int i=0;i<reqrd;i++)
{
cin>>temp;
tree.insert_item(temp);
}
}
else if(data_type==2)
{
cout<<"How many characters you want to insert ?"<<endl;
cin>>reqrd;
cout<<"Start entering the elements you want to insert into the tree !"<<endl;
for(int i=0;i<reqrd;i++)
{
cin>>temp1;
tree_1.insert_item(temp1);
}
}


SetConsoleTextAttribute(hconsole,8);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet


do
{
take_Action();  //menu call function

cin>>menu;
cout<<endl;
cout<<endl;

int integer_delete=0;
char character_delete=0;

int integer_search=0;
char character_search=0;
bool search_result=false;

if(menu==1)
{
if(data_type==1)
{
cout<<"Enter the element you want to delete !"<<endl;
cin>>integer_delete;
tree.delete_item(integer_delete);
cout<<endl;
cout<<endl;
SetConsoleTextAttribute(hconsole,10);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet
cout<<"After deleting the element from the tree the tree is "<<endl;
tree.temp_inorder_traversal();
cout<<endl;
cout<<endl;

}
else if(data_type==2)
{

cout<<"Enter the element you want to delete !"<<endl;
cin>>character_delete;
cout<<endl;
cout<<endl;
tree_1.delete_item(character_delete);
cout<<endl;
cout<<endl;
SetConsoleTextAttribute(hconsole,10);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet
cout<<"After deleting the element from the tree the tree is "<<endl;
tree_1.temp_inorder_traversal();
cout<<endl;
cout<<endl;
}

}
else if(menu==2)
{
if(data_type==1)
{
cout<<"Enter the integer you want to search ?"<<endl;
cin>>integer_search;
cout<<endl;
cout<<endl;
search_result=tree.search(integer_search);
if(search_result==true)
{
cout<<"The element is present in the tree !"<<endl;
}
else if(search_result==false)
{
cout<<"The element is not present in the tree !"<<endl;
}
cout<<endl;
cout<<endl;
}
else if(data_type==2)
{
cout<<"Enter the character you want to search ?"<<endl;
cin>>character_search;
cout<<endl;
cout<<endl;
search_result=tree_1.search(character_search);
if(search_result==true)
{
cout<<"The element is present in the tree !"<<endl;
}
else if(search_result==false)
{
cout<<"The element is not present in the tree !"<<endl;
}
cout<<endl;
cout<<endl;
}

}

if(menu==3)
{
if(data_type==1)
{
tree.print();
cout<<endl;
cout<<endl;

}
else if(data_type==2)
{
tree_1.print();
cout<<endl;
cout<<endl;
}

}
else if(menu==4)
{
if(data_type==1)
{
cout<<"The number of nodes in the tree is "<<endl;
cout<<tree.count_nodes();
cout<<endl;
cout<<endl;

}
else if(data_type==2)
{
cout<<"The number of nodes in the tree is "<<endl;
cout<<tree_1.count_nodes();
cout<<endl;
cout<<endl;
}

}
else if(menu==5)
{
if(data_type==1)
{
cout<<"The heigth of the tree is "<<endl;
cout<<tree.depth();
cout<<endl;
cout<<endl;


}
else if(data_type==2)
{

cout<<"The heigth of the tree is "<<endl;
cout<<tree_1.depth();
cout<<endl;
cout<<endl;

}

}
else if(menu==6)
{
if(data_type==1)
{
SetConsoleTextAttribute(hconsole,10);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet
cout<<"For comparison a second tree is needed !"<<endl;
cout<<"Follow the procedure below to input second tree !"<<endl;
cout<<endl;
cout<<endl;
BST_IMPLEMENT<int> tree_2;
cout<<"How many integer elements you want in second tree "<<endl;
cout<<"to which the previously entered tree is to"<<endl;
cout<<"be compared ?"<<endl;
cin>>reqrd_for_tree_2;
cout<<endl;
cout<<endl;
cout<<"Enter the elements for this new tree !"<<endl;
for(int i=0;i<reqrd_for_tree_2;i++)
{
cin>>temp_for_tree_2;
tree_2.insert_item(temp_for_tree_2);
}
cout<<endl;
cout<<endl;
if(tree==tree_2)
{
cout<<"The tree entered at start of program and freshly enetered tree are EQUAL !"<<endl;
}
else
{
cout<<"The tree entered at start of program and freshly enetered tree are NOT EQUAL !"<<endl;
}
cout<<endl;
cout<<endl;
}
else if(data_type==2)
{
SetConsoleTextAttribute(hconsole,10);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet
cout<<"For comparison a second tree is needed !"<<endl;
cout<<"Follow the procedure below to input second tree !"<<endl;
cout<<endl;
cout<<endl;
BST_IMPLEMENT<char> tree_3;
cout<<"How many character elements you want in second tree "<<endl;
cout<<"to which the previously entered tree is to"<<endl;
cout<<"be compared ?"<<endl;
cin>>reqrd_for_tree_3;
cout<<endl;
cout<<endl;
cout<<"Enter the elements for this new tree !"<<endl;
for(int i=0;i<reqrd_for_tree_3;i++)
{
cin>>temp_for_tree_3;
tree_3.insert_item(temp_for_tree_3);
}
cout<<endl;
cout<<endl;
if(tree_1==tree_3)
{
cout<<"The tree entered at start of program and freshly enetered tree are EQUAL !"<<endl;
}
else
{
cout<<"The tree entered at start of program and freshly enetered tree are NOT EQUAL !"<<endl;
}
cout<<endl;
cout<<endl;
}
}

else if(menu==7)
{
if(data_type==1)
{
SetConsoleTextAttribute(hconsole,10);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet
cout<<"Before mirroring the tree is "<<endl;
tree.temp_inorder_traversal();
cout<<endl;
cout<<endl;

tree.mirror_bst();

cout<<"After mirroring the tree is "<<endl;
tree.temp_inorder_traversal();
cout<<endl;
cout<<endl;

}
else if(data_type==2)
{
SetConsoleTextAttribute(hconsole,10);            //10=Green,1=Blue,12=RED,13=pink,6=yellow,8=violet
cout<<"Before mirroring the tree is "<<endl;
tree_1.temp_inorder_traversal();
cout<<endl;
cout<<endl;

tree_1.mirror_bst();

cout<<"After mirroring the tree is "<<endl;
tree_1.temp_inorder_traversal();
cout<<endl;
cout<<endl;
}
}
else if(menu==8)
{

if(data_type==1)
{
int height=tree.depth();

for(int i=1; i<=height; i++) 
{
cout << "Width of layer " << i << ": " << tree.getWidth(i) << "\n";
}
}
else if(data_type==2)
{
int height=tree_1.depth();

for(int i=1; i<=height; i++) 
{
cout << "Width of layer " << i << ": " << tree_1.getWidth(i) << "\n";
}

}



}
else if(menu==9)
{
if(data_type==1)
{

cout<<"SUM OF ALL PATHS ARE \n \n";
tree.printAllPath();

}
else if(data_type==2)
{
cout<<"SUM OF ALL PATHS(ASCII WOULD BE PRINTED FOR CHARACTERS) ARE \n \n";
tree_1.printAllPath();

}
}
}
while(menu!=-1);


system("pause");
return ;

}