Home Data Structures Insert, Search and Delete Operation in BST

Insert, Search and Delete Operation in BST

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:

  1. Go the root node of Tree, compare the value to be inserted with the current node value.
  2. 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.
  3. Compare the value again with the root node value of the subtree, and follow the step2 again.
  4. 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:

    1. Node to be deleted is a leaf node 
              10                                         10
           /     \         delete(9)                  /     \
          5       17        -------->                5      17
        /  \     /  \                              /       /  \
       3    9   16   18                           3       16   18

      If the node to be deleted is a leaf node, then we will delete it directly from the tree

    2. Node to be deleted have only one child
              10                                        10
           /     \           delete(5)                /     \
          5        17        -------->               8       17
           \      /  \                             /  \     /   \
            8    16   18                          7    9   16   18
          /  \                                    
         7    9

      If 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.

    3. 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     9
      

      If 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.

CPP Implementation of above Algorithm

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

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here