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
C-tutorial:-
- 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