 # Implementation of Binary search tree

Here in this post we are going to implement binary search tree . the language we are going to use is c++. But before writing the code first of all we have to know all about the binary search that means insertion , deletion , preorder , inorder and postorder traversal of the binary search tree . So first we will study all the these then after we will write code for implementing Binary search tree . So let’s get start …..

### What is binary search tree:-

Binary search tree is a node based binary tree data structure which has following properties:-

•    (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);
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)
{
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
1
Enter number of nodes you want to insert
6
Enter value of nodes
50 25 35 5 55 65
3
Preorder Traversal is:-
50 25 5 35 55 65
4
Inorder Traversal is:-
5 25 35 50 55 65