Write a CPP Program For Binary Search Tree

by

Aim:

To write a C++ program for binary search trees.

Description:

  • A Binary Search Tree (BST) is a tree in which all the nodes follow the below mentioned properties
  • The left sub-tree of a node has a key less than or equal to its parent node’s key.
  • The right sub-tree of a node has a key greater than to its parent node’s key.
  • Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as
    • left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Representation:

  • BST is a collection of nodes arranged in a way where they maintain BST properties.
  • Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.
  • Following is a pictorial representation of BST
  • Basic Operations
  • Following are the basic operations of a tree
    • Search − Searches an element in a tree.
    • Insert − Inserts an element in a tree.
    • Pre-order Traversal − Traverses a tree in a pre-order manner.
    • In-order Traversal − Traverses a tree in an in-order manner.
    • Post-order Traversal − Traverses a tree in a post-order manner.

Algorithm:

  1. Declare function create (), search (), delete (), Display ().
  2. Create a structure for a tree contains left pointer and right pointer.
  3. Insert an element is by checking the top node and the leaf node and the operation will
  4. be performed.
  5. Deleting an element contains searching the tree and deleting the item.
  6. Display the Tree elements.

Program:

#include<iostream.h>
#include<conio.h>
class bintree
{
typedef struct bst
{
int data;
struct bst *left,*right;
}
node;
node *root,*New,*temp,*parent;
public:
bintree()
{
root=NULL;
}
void create();
void display();
void delet();
void find();
void insert(node *,node*);
void inorder(node *);
void search(node**,int,node **);
void del(node *,int);
};
void bintree::create()
{
New=new node;
New->left=NULL;
New->right=NULL;
cout<<"\n enter the element";
cin>>New->data;
if(root==NULL)
root=New;
else
insert(root,New);
}
void bintree::insert(node *root,node *New)
{
if(New->data<root->data)
{
if(root->left==NULL)
root->left=New;
else
insert(root->left,New);
}
if(New->data>root->data)
{
if(root->right==NULL)root->right=New;
else
insert(root->right,New);
}
} 
void bintree::display()
{
if(root==NULL)
cout<<"tree is not created";
else
{
cout<<"\n the tree is: ";
inorder(root);
}
}
void bintree::inorder(node *temp)
{
if(temp!=NULL)
{
inorder(temp->left);
cout<<" "<<temp->data;
inorder(temp->right);
}
}
void bintree::find()
{
int key;
cout <<"\n enter the element which you want to search";
cin>>key;
temp=root;
search(&temp,key,&parent);
if(temp==NULL)
cout<<"\n element is not present";
else
cout<<"\n parent of node "<<temp->data<<" is"<<parent-
>data;
}
void bintree::search(node **temp,int key,node ** parent)
{
if(*temp==NULL)
cout<<endl<<" tree is not created"<<endl;
else
{
while(*temp!=NULL)
{
if((*temp)->data==key)
{
cout<<"\n the "<<(*temp)->data<<" element
is present";
break;
}
*parent=*temp;//stores the parent value
if((*temp)->data>key)
*temp=(*temp)->left;
else
*temp=(*temp)->right;
}
}
return;
} 
void bintree::delet()
{
int key;
cout<<"\n enter the element you want to delete";
cin>>key;
if(key==root->data)
{
bintree();// assigning a value NULL to root
}
else
del(root,key);}
void bintree::del(node *root,int key)
{
node *temp_succ;
if(root==NULL)
cout<<" tree is not created";
else
{
temp=root;
search(&temp,key,&parent);
if(temp->left!=NULL&&temp->right!=NULL)
{
parent=temp;
temp_succ=temp_succ->left;
while(temp_succ->left!=NULL)
{
parent=temp_succ;
temp_succ=temp_succ->left;
}
temp->data=temp_succ->data;
temp->right=NULL;
cout<<" now deleted it!";
return;
}
if(temp->left!=NULL&&temp->right==NULL)
{
if(parent->left==temp)
parent->left=temp->left;
else
parent->right=temp->left;
temp=NULL;
delete temp;
cout<<" now deleted it!";
return;
}
if(temp->left==NULL&&temp->right!=NULL)
{
if(parent->left==temp)
parent->left=temp->right;
else
parent->right=temp->right;
temp=NULL;
delete temp;
cout<<" now deleted it!";
return;}
/*deleting a node which is having no child*/
if(temp->left==NULL&&temp->right==NULL)
{
if(parent->left==temp)
parent->left=NULL;
else
parent->right=NULL;
cout<<" now deleted it!";
return;
}
}
}
void main()
{
int choice;
char ans='N';
bintree tr;
clrscr();
cout<<"\n\t program for binary search tree";
cout<<"\n1.create\n2.search\n3.delete\n4.display";
do
{
cout<<"\n\n enter your choice:";
cin>>choice;
switch(choice)
{
case 1:do
{
tr.create();
cout<<"do you want to enter more elements:
(y/n)"<<endl;
ans=getche();
}
while(ans=='y');
break;
case 2:tr.find();
break;
case 3:
tr.delet();
break;
case 4:
tr.display();
break;
}
}
while(choice!=5);
}

Output:

Result:

Thus the C++ program for binary search tree was created, executed and output was verified successfully.

Leave a Comment