We have already discussed the Tree data structure and a Binary Search Tree. So here we are going to discuss insert, search & delete operations in BST:
1)Insertion
2)Search
3)Deletion
Insertion
The basic Binary Search tree property says that, if an element is greater then the root node, it will be present in the right subtree and if it is smaller then the root node then it will be present in the left subtree. So, for insertion, we will use this basic property of BST
Algorithm:
- Go the root node of Tree, compare the value to be inserted with the current node value.
- If the value to be inserted is smaller then or equal to the root node value, go to the left subtree, else go to the right subtree.
- Compare the value again with the root node value of the subtree, and follow the step2 again.
- On reaching the end node, insert the value left(if the value is smaller then current node value), else right.
insert_BST(value, tree){
if(tree == NULL)
return new Node(value);
if(tree->value >= value)
tree->left = insert_BST(value, tree->left)
else
tree->right = insert_BST(value, tree->right)
return tree;
}
Search
We will follow here logic similar to insertion i.e if the node if the root node value is equal to the value to be searched, then we will return search is successful, else if the root node value is less then the value to be searched, then we will move to the left subtree to find the element, else we will move to the right subtree to search the element.
Algorithm
search_BST(value, tree){
if (tree == NULL)
return "tree is empty";
if(tree->value == value)
return "search is successful";
else if (tree->value > value)
search_BST(value, tree->left);
else
search_BST(value, tree->right);
}
Deletion
Deletion is a little tricky is Binary Search Tree. One important thing to consider is that after a deletion operation any of the BST property should not be violated.
Algorithm
In deletion operation any of the 3 cases will arise:
-
- Node to be deleted is a leaf node
10 10 / \ delete(9) / \ 5 17 --------> 5 17 / \ / \ / / \ 3 9 16 18 3 16 18If the node to be deleted is a leaf node, then we will delete it directly from the tree
- Node to be deleted have only one child
10 10 / \ delete(5) / \ 5 17 --------> 8 17 \ / \ / \ / \ 8 16 18 7 9 16 18 / \ 7 9If the node to be deleted has only one child node, then we will delete the node and attach its child( left or right) to its parent node. Here we deleted node 5 and attached its child 8 to its parent node 10.
- Node to be deleted have both the child
10 10 / \ delete(5) / \ 5 17 --------> 4 17 / \ / \ / \ / \ 2 8 16 18 2 8 16 18 / \ / \ / / \ 1 4 7 9 1 7 9 OR 10 10 / \ delete(5) / \ 5 17 ----------> 7 17 / \ / \ / \ / \ 2 8 16 18 2 8 16 18 / \ / \ / \ \ 1 4 7 9 1 4 9If the node to be deleted has both the child, then delete the node and replace it with either the rightmost child of its left successor or the leftmost child of its right successor. Here in the 1st tree, we replaced 5 with the rightmost child 4 of its left successor 2 and in the second tree, we replaced 5 with the leftmost child 7 of its left successor 8.
- Node to be deleted is a leaf node
CPP Implementation of above Algorithm
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node *left;
Node *right;
public:
Node(int x){
data = x;
left = NULL;
right = NULL;
}
};
Node *insert_BST(Node *tree, int val)
{
if(tree == NULL){
cout<<val <<" is inserted into BST successfully"<<endl;
return (new Node(val));
}
if(tree->data >= val)
tree->left = insert_BST(tree->left, val);
else
tree->right = insert_BST(tree->right, val);
return tree;
}
int search_BST(Node *tree, int val)
{
if(tree == NULL){
cout<<val<<" is not present in the tree\n";
return 0;
}
string ret_val;
if(tree->data == val)
cout<<val<<" is present in the tree\n";
else if(tree->data > val)
search_BST(tree->left, val);
else
search_BST(tree->right, val);
return 0;
}
Node* delete_BST(Node *tree, int val)
{
if(tree == NULL){
cout<<"value is not present in BST"<<endl;
return tree;
}
if(tree->data > val)
tree->left = delete_BST(tree->left, val);
else if(tree->data < val)
tree->right = delete_BST(tree->right, val);
else{
//if left child of the node is empty
if(tree->left == NULL){
Node *temp = tree->right;
free(tree);
tree= temp;
}
//if right child of the node is empty
else if(tree->right == NULL){
Node *temp = tree->left;
tree = temp;
free(temp);
}
//if both left and right child exists for the node
else{
Node *temp = tree->left;
while(temp->right->right!=NULL){ // traverse until you don't reach, the second last right node of the left child of node to be deleted
temp = temp->right;
}
tree->data = temp->right->data; // update the value to be deleted with the value of the rightmost node
Node *temp2 = temp->right->left; // pointer to the left child of the last right node
free(temp->right); // delete the last node
temp->right = temp2; // assign the left child of last right node to second last right node
}
}
return tree;
}
void inorder(Node *tree)
{
if (tree != NULL)
{
inorder(tree->left);
cout<<tree->data<<" ";
inorder(tree->right);
}
}
int main(){
Node *tree;
tree = new Node(10);
tree->left = new Node(5);
tree->left->left = new Node(2);
tree->left->right = new Node(8);
tree->left->left->left = new Node(1);
tree->left->left->right = new Node(4);
tree->left->right->left = new Node(7);
tree->right = new Node(17);
tree->right->left = new Node(16);
tree->right->right = new Node(18);
insert_BST(tree, 9);
cout<<"inorder traversal of the current tree is: ";
inorder(tree);
cout<<endl;
search_BST(tree,9);
tree = delete_BST(tree,5);
cout<<"deleted 5 successfully \n";
search_BST(tree,5);
cout<<"inorder traversal of the current tree is: ";
inorder(tree);
cout<<endl;
return 0;
}
Time Complexity
The time complexity of Insert operation is O(N), Search Operation is O(N) & Delete Operation is O(N), where N is the number of nodes in BST. Note, this worst-case time complexity and will occur when the tree is left or right-skewed.
This is how we will perform insert, search & delete operation in Binary Search Tree (BST).