Binary Search Tree

Binary Search Tree

Definition: A Binary Search Tree is a binary tree in which :

• Left subtree contains only nodes with values less than the node's value.

• Right subtree contains only nodes with values greater than the node's value.  

• Both left and right subtrees must also be binary search trees.

The binary search tree is based on the binary search algorithm. While creating the binary search tree the data is systematically arranged. That means values at left subtree < root node value < Right subtree values. See the Fig. 6.6.1.

If you observe the Fig. 6.6.1 carefully, you will find that the left value < parent value < right value is followed throughout the tree.

 

Various operations that can be performed on binary search tree are ‒

1. Insertion of a node in a binary tree.

2. Deletion of some element from the binary search tree.

3. Searching of an element in the binary tree.

4. Display of binary tree.

 

Let us discuss each operation one by one ‒

1. Insertion of a node in a binary tree

Algorithm:

1. Read the value for the node which is to be created, and store it in a node called New.

2. Initially if (root!=NULL) then root=New.

3. Again read the next value of node created in New.

4. If (New‒>value  <  root‒>value) then attach New node as a left child of root otherwise attach New node as a right child of root.

5. Repeat step 3 and 4 for constructing required binary search tree completely.

void bintree::insert(node *root,node *New)

{

if(New‒>data < root‒>data)

{

   if(root‒>left= =NULL)   // Attaching left node to the current node.

   root‒>left=New;

else

   insert(root‒>left,New);   // If the root node has already some left child, then move on to left subtree

}

if(New‒>data>root‒>data)

{

   if(root‒>right= =NULL)

   root‒>right=New;

else

   insert(root‒>right,New);

}

}

While inserting any node in binary search tree, first of all we have to look for its appropriate position in the binary search tree. We start comparing this new node with each node of the tree. If the value of the node which is to be inserted is greater than the value of current node we move on to the right sub‒branch otherwise we move on to the left sub‒branch. As soon as the appropriate position is found attach this new node as left or right child appropriately.

In the Fig. 6.6.2 if we want to insert 23. Then we will start comparing 23 with value of root node i.e. 10. As 23 is greater than 10, we will move on right sub‒tree. Now we will compare 23 with 20 and move right, compare 23 with 22 and move right. Now compare 23 with 24 but it is less than 24. We will move on left branch of 24. But as there is NULL node as left child of 24, we can attach 23 as left child of 24.

 

2. Deletion of an element from the binary tree

For deletion of any node from binary search tree there are three cases which are possible.

i. Deletion of leaf node.

ii. Deletion of a node having one child.

iii. Deletion of a node having two children.

Let us discuss the above cases one by one.

i. Deletion of leaf node.

This is the simplest deletion, in which we set the left or right pointer of parent node as NULL.

From the above tree, we want to delete the node having value 6 then we will set left pointer of its parent node as NULL. That is left pointer of node having value 8 is set to NULL.

ii. Deletion of a node having one child.

To explain this kind of deletion, consider a tree as given below.

If we want to delete the node 15, then we will simply copy node 18 at place of 15 and then set the node free. The inorder successor is always copied at the position of a node being deleted.

iii. The node having two children

Again, let us take some example for discussing this kind of deletion.

Let us consider that we want to delete node having value 7. We will then find out the inorder successor of node 7. The inorder succesor will be simply copied at location of  node 7. Thats it!

That means copy 8 at the position where value of node is 7. Set left pointer of 9 as NULL. This completes the deletion procedure.

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);

   //temp node is to be deleted

   /*deleting a node with two children*/

if(temp‒>left! =NULL&&temp‒>right!=NULL)

{

   parent=temp;

   temp_succ=temp‒>right;  //temp is node which is to be deleted. Parent is a node which keeps track of parent node. temp and temp_succ is for keeping track of successor of temp node.

   while(temp_succ‒>left!= NULL)

   {

      parent = temp_succ;

      temp_succ=temp_succ‒>left; <‒‒‒‒‒‒‒‒‒‒‒Moving to leftmost sub‒tree

// Copying the successor node's data to temp node. Thus contents of temp node gets deleted.

   }

   temp‒>data=temp_succ‒>data;

   //copying the immediate successor

   temp‒>right=NULL;

   cout<<" Now Deleted it!";

   return;

}

/*deleting a node having only one child*/

/*The node to be deleted has left child*/

if(temp‒>left!= NULL &&temp‒>right= = NULL)

{

   if(parent‒>left= =temp)<‒‒‒‒‒‒‒‒‒‒‒ Finding the parent of temp

      parent‒>left=temp‒>left;

   else

      parent‒>right=temp‒>left;

   temp=NULL;

   delete temp;

   cout<<" Now Deleted it!";

   return;

}

/*The node to be deleted has right child*/

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;

}

}

}

 

3. Searching a node from binary search tree.

Algorithm

1. The node which is to be searched in the BST is assumed as key node.

2. Compare key node with root node, assume it as current node.

3. If value of key node is greater than current node then we search on right sub branch.

4. If value of key node is less than current node then we search on left sub branch.

5. If value of key node is equal to current node then we declarer "node is found".

6. Otherwise we declare "node is not found".

In the above tree, if we want to search for value 9. Then we will compare 9 with root node 10. As 9 is less than 10 we will search on left sub‒branch. Now compare 9 with 5, but 9 is greater than 5. So we will move on right sub‒branch. Now compare 9 with 8 but as 9 is greater than 8 we will move on right sub‒branch. As the node we will get holds the value 9. Thus the desired node can be searched. Let us see the 'C' implementation of it.

The routine is as given below.

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<<"\nThe"<<(*temp)‒>data<<"Element is Present";

         break;

      }

   *parent=*temp://stores the parent value<‒‒‒‒‒‒ //• Marking the parent node

   if((*temp)‒>data>key) <‒‒‒‒‒‒  //• If current node is greater than key

      *temp=(*temp)‒>left; <‒‒‒‒‒‒  //• Search for the left subtree

   else

      *temp=(*temp)‒>right;

}

}

return;

}

We can display a tree in inorder fashion. Hence the complete implementation is given below along with appropriate output.

   /**************************************************************************

Program For Implementation Of Binary Search Tree and perform insertion deletion,searching,display of tree.

**************************************************************************/

#include<iostream>

using namespace std;

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<<"\nParent 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<<"\nThe"<<(*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 U wish to Delete";

cin>>key;

if(key= =root‒>data)

{

bintree();//assigning a value NULL to root

}

else

del(root,key);

}

/*

This function is for deleting a node from binary search tree. There exist three possible cases for deletion of a node

*/

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);

//temp node is to be deleted

/*deleting a node with two children*/

if(temp‒>left!=NULL&&temp‒>right!=NULL)

{

parent=temp;

temp_succ=temp‒>right;

while(temp_succ‒>left!= NULL)

{

parent=temp_succ;

temp_succ=temp_succ‒>left;

}

temp‒>data=temp_succ‒>data;

//copying the immediate successor

temp‒>right = NULL;

cout<<" Now Deleted it!":

return;

}

/*deleting a node having only one child*/

/*The node to be deleted has left child*/

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;

}

/*The node to be deleted has right child*/

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;

cout<<"\n\t Program For Binary Search Tree ";

do

{

cout<<"\n1.Create\n2.Search\n3.Delete\n4.Display";

cout<<"\n\n Enter your choice :";

cin>>choice;

switch(choice)

{

case 1:do

       {

       tr.create();

       cout<<"Do u 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

Program For Binary Search Tree

1.Create

2.Search

3.Delete

4.Display

Enter your choice :1

Enter The Element 10

Do u Want To enter More elements?(y/n)

y

Enter The Element 8

Do u Want To enter More elements?(y/n)

y

Enter The Element 7

Do u Want To enter More elements? (y/n)

y

Enter The Element 9

Do u Want To enter More elements?(y/n)

y

Enter The Element 12

Do u Want To enter More elements?(y/n)

y

Enter The Element 11

Do u Want To enter More elements?(y/n)

y

Enter The Element 13

Do u Want To enter More elements?(y/n).

n

1.Create

2.Search

3.Delete

4.Display

Enter your choice :4

The Tree is : 7 8 9 10 11 12 13

1.Create

2.Search

3.Delete

4.Display

Enter your choice :2

Enter The Element Which You Want To Search 13

The13Element is Present

Parent of node 13is 12

1.Create

2.Search

3.Delete

4.Display

Enter your choice :3

Enter The Element U wish to Delete 12

The 12 Element is Present Now Deleted it!

1.Create

2.Search

3.Delete

4.Display

Enter your choice :4

The Tree is: 7 8 9 10 11 13

1.Create

2.Search

3.Delete

4.Display

Enter your choice :3

Enter The Element U wish to Delete 11

The11Element is Present Now Deleted it!

1.Create

2.Search

3.Delete

4.Display

Enter your choice :4

The Tree is : 7 8 9 10 13

1.Create

2.Search

3.Delete

4.Display

Enter your choice :3

Enter The Element U wish to Delete7

The7Element is Present Now Deleted it!

1.Create

2.Search

3.Delete

4.Display

Enter your choice :4

The Tree is: 8 9 10 13

1.Create

2.Search

3.Delete

4.Display

Enter your choice :5

 

Example : 1

Draw the binary search tree for the following input list 25, 45, 12, 60, 75, 92, 10. Trace an algorithm to delete the nodes 25, 75, 10 from the tree.

Solution : The creation of binary search tree is :

The deletion of nodes 25, 75 and 10 is as follows:

Step 1 :

Delete 25

The node 25 is the root node. The inorder successor of node 25 is 45. We will replace 25 by 45. Thus the binary search tree then becomes as follows:

Step 2 :

Delete 75

The node 75 has only one right child. We will replace 75 by 92. And then 75 will be removed. The binary tree then becomes :

Step 3 :

Delete 10

The node 10 is a leaf node. Hence simply make it NULL. The binary search tree will then be as follows:

Review Questions

1. Give an algorithm for searching in BST.

             OR

Write algorithm to locate an element from binary search tree.

2. Write the routines to insert and remove a node from binary search tree.