C++ program to implement binary search tree

C++ program to implement binary search tree and perform insertion, deletion, searching, display of tree.

C++ program to implement binary search tree

#include<iostream>
using namespace std;
struct tree_node
{
    int data;
    tree_node *left,*right;
};
class binary_search_tree
{
    int item;
    tree_node *root;
    void put_in_parent(tree_node *parent,tree_node *temp,tree_node *temp1)
    {
        if(parent->left==temp)
            parent->left=temp1;
        else
            parent->right=temp1;
    }
public:
    binary_search_tree()
    {
        root=NULL;
    }
    void getdata();
    void insert(tree_node **);
    void delete_node();
    void search();
    void display(tree_node *);
    tree_node** getroot()
    {
        return &root;
    }
};
void binary_search_tree::getdata()
{
    cout<<"Enter the element ";
    cin>>item;
}
void binary_search_tree::insert(tree_node **temp)
{
    if(*temp==NULL)
    {
        tree_node *ne;
        ne=new tree_node;
        ne->data=item;
        ne->right=ne->left=NULL;
        *temp=ne;
        return;
    }
    else if(item<(*temp)->data)
        insert(&((*temp)->left));
    else if(item>(*temp)->data)
        insert(&((*temp)->right));
    else
    {
        cout<<"Duplicate values not allowed ";
        return;
    }
}
void binary_search_tree::delete_node()
{
    tree_node *parent=NULL,*temp=root;
    while(temp->data!=item)
    {
        parent=temp;
        if(item<temp->data)
            temp=temp->left;
        else if(item>temp->data)
            temp=temp->right;
        if(temp==NULL)
        {
            cout<<"Element not found "<<endl;
            return;
        }
    }
    if(temp->left!=NULL&&temp->right!=NULL||temp==root)
    {
        if(root->left==NULL&&root->right==NULL)
            root=NULL;
        else if(temp->right==NULL)
             root=root->left;
        else if(temp->left==NULL)
             root=root->right;
        else if((root->right)->left==NULL)
        {
            (root->right)->left=root->left;
            root=root->right;
        }
        else
        {
            tree_node *temp1=temp;
            temp=temp->right;
            while(temp->left!=NULL)
            {
                parent=temp;
                temp=temp->left;
            }
            temp1->data=temp->data;
            parent->left=temp->right;
        }
    }
    else if(temp->left==NULL&&temp->right==NULL)
        put_in_parent(parent,temp,NULL);
    else if(temp->left==NULL)
        put_in_parent(parent,temp,temp->right);
    else
        put_in_parent(parent,temp,temp->left);
    delete temp;
    cout<<"Element Successfully deleted "<<endl;
}
void binary_search_tree::search()
{
    tree_node *temp=root,*parent=NULL;
    int flag=1;
    while(temp!=NULL)
    {
        if(temp->data==item)
        {
            cout<<"Element is present "<<endl;
            if(parent!=NULL)
                cout<<"Parent node of "<<item<<" is "<<parent->data<<endl;
            return;
        }
        parent=temp;
        if(item<temp->data)
            temp=temp->left;
        else
            temp=temp->right;
    }
    cout<<"Element is not present ";
}
void binary_search_tree::display(tree_node *temp)
{
    if(temp==NULL)
        return;
    display(temp->left);
    cout<<temp->data<<" ";
    display(temp->right);
}
int main()
{
    binary_search_tree tree;
    int a,flag=1;
    while(flag)
    {
        cout<<"Main Menu\n\t1.) Insertion\n\t2.) Deletion\n\t3.) Search\n\t4.) Display\n\t5.) Exit";
        cout<<"\nEnter your choice ";
        cin>>a;
        switch(a)
        {
        case 1:
            tree.getdata();
            tree.insert(tree.getroot());
            break;
        case 2:
            tree.getdata();
            tree.delete_node();
            break;
        case 3:
            tree.getdata();
            tree.search();
            break;
        case 4:
            tree.display(*(tree.getroot()));
            cout<<endl;
            break;
        case 5:
            flag=0;
            break;
        default:
            cout<<"Wrong choice "<<endl;
        }
    }
}