Implementation of Binary search tree

• The left subtree of a node contains only nodes which has the less value.
• The right subtree of a node contains only nodes which has the greater value .
• The left and right subtree each must also be a binary search tree.
• 

  Tree traversal of the binary search tree:-

•    (a) Inorder (Left, Root, Right) : 4 2 5 1 3
  (b) Preorder (Root, Left, Right) : 1 2 4 5 3
  (c) Postorder (Left, Right, Root) : 4 5 2 3 1

Deletion in binary search tree :-

There are three cases in deletion of a node in binary search tree.

case 1 : if node to be deleted has no children 

In this case if node is root then we simply replace it by root=NULL . otherwise  if parent is the pointer which is denoted the parent node of the node to be deleted then ..if parent->left==curr (i.e node to be deleted is the left child of the parent ) then parent->left = NULL similarly for the right child.

case 2: if node to be deleted has two children 

In this case we replace the node by it’s inorder successor.

Case 3: if node to be deleted has one children

In this case if it is root node then root=NULL otherwise if parent  is the parent node of the node to deleted and the it is left child of the parent then parent->left=NULL similarly for the right children.

Code (Implementation of Binary search tree):-

#include<bits/stdc++.h>
using namespace std;


// defining the structure of the node 
struct node
{
    int data;
    struct node *left,*right;
};
struct node *root=NULL;

// function for creating node 
struct node *CreateNode()
{
    struct node *temp;
    temp=(struct node *) malloc(sizeof(struct node));
    return temp;
}

// function for insert the element into Binary Tree
void insert(int e)
{
    struct node *tem,*t;
    tem=CreateNode();
    tem->data=e;
    tem->left=NULL;
    tem->right=NULL;
    if(root==NULL)
    {
        root=tem;
    }
    else
    {
        t=root;
        while(t!=NULL)
        {
            if(t->data>tem->data)
            {
                if(t->left==NULL)
                {
                    t->left=tem;
                    t=t->left;
                }
                t=t->left;
            }
            else
            {
                if(t->right==NULL)
                {
                    t->right=tem;
                    t=t->right;
                }
                t=t->right;
            }
        }
        
    }
    
}

// function for searching the element 
void searchkey(struct node *&curr,int a,struct node *&parent)
{
    while(curr!=NULL && curr->data!=a)
    {
        parent=curr;
        if(curr->data>a)
        {
            curr=curr->left;
        }
        else
          curr=curr->right;
    }
}

// function for finding the inorder successor 
struct node *getInorderSuccessor(struct node* curr)
{
    while(curr->left!=NULL)
      curr=curr->left;
    return curr;
}

// function for deleting the node form Binary search tree 
void deleteNode(int a)
{
    // for storing the parent of the curr pointer 
    struct node *parent=NULL;
    
    // curr poiner 
    struct node *curr;
    curr=root;
    searchkey(curr,a,parent);
    //return if key is not found in the tree 
    if(curr==NULL)
     return;
    
    // case :1 if node to be deleted has no children 
    if(curr->left==NULL && curr->right==NULL)
    {
        //if node to be deleted is root node then
        if(curr==root)
        {
            root=NULL;
        }
        else
        {
            // curr is the left child then
            if(parent->left==curr)
              parent->left=NULL;
            // otherwise
            else
              parent->right=NULL;
        }
    }
    else
    {
         // case :2 if node to be deleted has 
         // two children
         if(curr->left && curr->right)
         {
             // find inorder successor node 
             struct node *successor= getInorderSuccessor(curr->right);
             
             // store the value of successor
             int val=successor->data;
             
             // recursively delete the successor
             deleteNode(successor->data);
             
             // copy the value of successor to the curr node 
             
             curr->data=val;
             
             
         }
         //case 3:  if node to be deleted has one children
         else
         {
             // choose a child that means
             // which child is present in the tree 
             struct node * child=(curr->left) ? curr->left : curr->right;
             
             // if node is to be deleted is root then
             if(curr==root)
             {
                 root=child;
             }
             // otherwise
             else
             {
                if(curr==parent->left)
                  parent->left=child;
                else
                  parent->right=child;
             }
             
             free(curr);
         }
         
        
    }
    
}

// function for preorder Traversal
void preorderTreversal(struct node *tem)
{
    if(tem)
    {
        cout<<tem->data<<" ";
        preorderTreversal(tem->left);
        preorderTreversal(tem->right);
    }
}

// function for inorder Traversal
void InorderTraversal(struct node *temp)
{
    if(temp)
    {
        InorderTraversal(temp->left);
        cout<<temp->data<<" ";
        InorderTraversal(temp->right);
    }
}

// function for Postorder Traversal
void PostorderTraversal(struct node *temp)
{
    if(temp)
    {
        PostorderTraversal(temp->left);
        PostorderTraversal(temp->right);
        cout<<temp->data<<" ";
    }
}



// Driver function
int main()
{
    int ch,n,e;
    cout<<"1. Insert new node in the Binary Tree"<<endl;
    cout<<"2. Delete node from the Binary Tree"<<endl;
    cout<<"3. preoreder Traversal"<<endl;
    cout<<"4. Inorder Traversal"<<endl;
    cout<<"5. Postorder Traversal"<<endl;
    cout<<"6.Exit"<<endl;
    while(1)
    {
        cout<<"Enter your choice"<<endl;
        cin>>ch;
        switch(ch)
        {
            case 1: cout<<"Enter number of nodes you want to insert"<<endl;
                    cin>>n;
                    cout<<"Enter value of nodes"<<endl;
                    for(int i=0;i<n;i++)
                    {
                        scanf("%d",&e);
                        insert(e);
                    }
                    break;
            case 2: cout<<"Enter the value of node which you want to delete"<<endl;
                    cin>>e;
                    deleteNode(e);
                    break;
                    
            case 3: cout<<"Preorder Traversal is:-"<<endl;
                    preorderTreversal(root);
                    cout<<"\n";
                    break;
            case 4: cout<<"Inorder Traversal is:-"<<endl;
                    InorderTraversal(root);
                    cout<<"\n";
                    break;
            case 5: cout<<"Postorder Traversal is:-"<<endl;
                    PostorderTraversal(root);
                    cout<<"\n";
                    break;
            case 6: exit(0);
                    break;
            default: cout<<"Wrong input"<<endl;
        }
    }
    
    
    return 0;
}

Output:-

1. Insert new node in the Binary Tree
2. Delete node from the Binary Tree
3. preoreder Traversal
4. Inorder Traversal
5. Postorder Traversal
6.Exit
Enter your choice
1
Enter number of nodes you want to insert
6
Enter value of nodes
50 25 35 5 55 65
Enter your choice
3
Preorder Traversal is:-
50 25 5 35 55 65 
Enter your choice
4
Inorder Traversal is:-
5 25 35 50 55 65 
Enter your choice
5
Postorder Traversal is:-
5 35 25 65 55 50 
Enter your choice
2
Enter the value of node which you want to delete
25
Enter your choice
4
Inorder Traversal is:-
5 35 50 55 65 
Enter your choice