Tuesday, 26 September 2017

Binary Search Tree implementation in C++ 

Implementation of Binary Search Tree with its different operation like inserting a new node, traversing BST ( pre-order, in-order, post-order), Deletion in BST ( deletion of a leaf node, deletion of the node having a child, deletion of a node having two children) in C++  language.

Implementation of different function of BST is divided into different sections according to their working. All these functions are fully tested on Online compiler like www.jdoodle.com, www.codechef.com etc. If you want to check the full functionality of this program then please check the link given at the end of this blog:

Section 1: In this section, all the header file, as well as required function, are declared which we want to use in this program.
#include <iostream>
using namespace std;
int ext=0,total=0;
node * create_bst(node *root, int val);
void inorder(node *root);
void postorder( node *root);
void preorder(node *root);
void searchelement(node *root,int val);
struct node *DeleteNodeInBST( node *root,int val);
struct node * minValueNode( node* node);

Section 2: In this section, a structure of the Binary search tree node are declared with the help of structure datatypes of C++ language. In this node structure, int info part is declared to insert data part of a node and *left and *right pointer are used to store the address of left and right child of a root node.
struct node
{
int info;
node *left;
node *right;
}; 

Section 3: In this section, the main function of this program is implemented where different function call is made.
int main()
{
node *root=NULL;
int n,val,i,vale,valu,val1;
cin>>n;
for(i=0;i<n;i++)
{
cin>>val;
root=create_bst(root,val);
}
cout<<"in order"<<endl;
inorder(root);
cout<<"post order"<<endl;
postorder(root);
cout<<"pre order"<<endl;
preorder(root);
cout<<endl;
cout<<"total nodes="<<total<<endl;
cout<<"external nodes:"<<ext<<endl;
cout<<"internal nodes:"<<total-ext<<endl;
cin>>vale;
searchelement(root,vale);
cin>>val1;
root=DeleteNodeInBST(root,val1);
cout<<"in order"<<endl;
inorder(root);
}

Section 4: In this section, the functionality of create_bst are implemented with its different condition. Keep in mind that this function always returns address of root node to main() function.
node *create_bst( node *root, int val)
{
if(root==NULL)
{
root=new node;
root->info=val;
root->left=NULL;
root->right=NULL;
}
else if(val<=root->info)
{
root->left=create_bst(root->left,val);
}
else
{
root->right=create_bst(root->right,val);
}
return root;
}

Section 5: In this section, the functionality of inorder(), preorder() and inorder()  are implemented with its different conditions. As we know in pre-order traversing we process root-left-right node, inorder traversing we process left-root-right, postorder traversing we process left-right-root.
void inorder(struct node *root)
{
if(root!=NULL)
{
total++;
if(root->left==NULL && root->right==NULL)
ext++;
inorder(root->left);
cout<<root->info<<" ";
inorder(root->right);
}
}
void postorder(struct node *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
cout<<root->info<<" ";
}
}
void preorder(struct node *root)
{
if(root!=NULL)
{
cout<<root->info<<" ";
preorder(root->left);
preorder(root->right);
}
}

Section 6: In this section, we are implementing a function which is going to search a key element into the Binary Search tree. If the root of the Binary search tree is NULL then key not found in it.
void searchelement(struct node *root2, int val)
{
if(root2==NULL)
{
cout<<"not found";
}
else if(root2->info==val)
{
cout<<"found= "<<val;
}
else if(val<=root2->info)
{
return searchelement(root2->left,val);
}
else
{
return searchelement(root2->right,val);
}
}

Section 7: In this section, we write a function to find out the minimum element in any left sub-tree of any node.
struct node * minValueNode(struct node* node)
{
node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}

Section 8: In this section, we write a function to delete any node from the Binary Search tree. We have three option for deleting any node.
1. When the deleted node is a leaf node
2. When the deleted node is a node having single child
3. When the deleted node is a node having two children
struct node *DeleteNodeInBST(struct node *root,int key)
{
if (root == NULL) 
{
return root;
}
if (key < root->info)
{
root->left = DeleteNodeInBST(root->left, key);
}
else if (key > root->info)
{
root->right = DeleteNodeInBST(root->right, key);
}
else
{
if (root->left == NULL)
{
struct node *temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
delete root;
return temp;
}
struct node* temp = minValueNode(root->right);
root->info = temp->info;
root->right = DeleteNodeInBST(root->right, temp->info);
}
return root;
}


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput