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:
 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
 Primary test
 Sum or difference
 point and line
Wipro :
 Update the booking ID  Wipro previous year question paper solution
 Pages in PDF
 Find the location id
 Find the odd digits
 Find the Product ID
Infytq :
Key Points;
Hackerrank:
 Python : missing characters : hackerrank solution
 Python : string transformation  Hackerrank solution
 Active Traders certification test problem  Hackerrank Solution
 Usernames changes certification test problem  Hackerrank Solution
 string Representation of objects certification test hackerrank solution
 Average Function  hackerrank certification problem solution
Ctutorial:
 Micros in C
 Pointer in c
 Function declaration
 Types of user define function
 return type of function
 2D array
See more:
 c program to convert specified days into years weeks and days
 Print Reverse Hollow Pyramid
 Update the booking ID  Wipro previous year question paper
 Pages in PDF  Wipro previous year question paper
 Sparse Matrix in data structure
 Find the location ID  Wipro previous year Coding question
 find the odd digits  Wipro Coding question
 Find the product id  Wipro Coding question
 Difference between static and dynamic memory allocation
 What is asymptotic Notation