Deletion In Binary Search Tree In C++

Deletion In Binary Search Tree:

A binary search tree is a tree in which the data in left subtree is less than the root and the data in right subtree is greater than the root. There are three cases in deletion .In this article, deletion is performed in C++.

 

C++ Program To Delete in BST
Example of BST - C++ Program To Delete Element in BST

Three Possible Cases In Deletion:

  1. The node to be deleted has no children.
  2. The node to be deleted has 2 children.
  3. The node to be deleted has 1 child.
  4. In this example, 8, 13 and 18 are going to be deleted.

Case 1: The node to be deleted has no child nodes.

If the node to be deleted from the tree has no child nodes, the node is simple deleted from the tree since it is a leaf node.

Step 1:
  • The node to be deleted is 8.
Step 2:
  • Since the node 8 is a leaf node consisting of no child nodes, it is simply removed from the tree.
  • The BST structure after deletion is shown as follows.
Step 1 and Step 2 - C++ Program To Delete in BST

Case 2: The node to be deleted has a single child node

 If the node to be deleted has a single child node, the target node is replaced from its child node and then the target node is simply deleted.

Step 3:
  • The node to be deleted is 13.
Step 4:
  • Since the target node has a single child, i.e, 14, we replace the node 13 with node 14.
  • The BST structure after deletion is shown as follows.
Step 3 and 4 - C++ Program To Delete In BST

Case 3: The node to be deleted has two child nodes

If the node to be deleted has two child nodes, we first find the inorder successor of the node and replace the target node with the inorder successor.

Step 5:
  • The next node to be deleted is 18.
Step 6:
  •  We can see from the image given that the target node 18 has two child nodes.
  • We find the inorder successor of the target node. In this case the inorder successor is 19. Inorder successor can be defined as the smallest element of the right subtree.
  • After replacing the target node with the inorder successor, the node is simply deleted.
  • The final BST is shown as follows
STep 5 and Step 6 - C++ Program To Delete in BST

Code:

#include <bits/stdc++.h>
using namespace std;
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
void inorder_traversal (Tree *root) {
    if (root == NULLreturn;
    // Visit Left subtree
    inorder_traversal(root -> left);
      // Print the data
    cout << root -> data << ” “;
    // Visit right subtree
    inorder_traversal(root -> right);
  
}
Tree* Delete(Tree* rootint x) {
    // If leaf is encountered
    if (root == NULL) {
        cout << “Node not found “;
        return NULL;
    }
    // Recur for left subtree
    if (root -> data > x) {
        root -> left = Delete(root -> left, x);
    }
    // Recur for right subtree
    else if (root -> data < x){
        root -> right = Delete(root -> right , x);
    }
    else {
        // Left child NULL
        if (root -> left == NULL) {
            Tree *temp = root -> right;
            free(root);
            return temp;
        }
        // Right child NULL
        else if (root -> right == NULL) {
            Tree *temp = root -> left;
            free(root);
            return temp;
        }
        else {
            // Finding the inorder successor
            Tree *temp = root -> right;
            // Finding the leftmost node in right subtree
            while (temp -> left != NULL) temp = temp -> left;
            // Changing value of root
            root -> data = temp -> data;
            // Deleting the leftmost node;
            root -> right = Delete(root -> righttemp -> data); 
        }
    }
    return root;
    
}
int main() {
    Tree *root = new Tree(15);
    root -> left = new Tree(13);
    root -> right = new Tree(18);
    root -> left -> left = new Tree(8);
    root -> left -> right = new Tree(14);
    root -> right -> left = new Tree(16);
    root -> right -> right = new Tree(19);
    int first_delete = 8, second_delete = 13, third_delete = 18;
    cout << “Inorder Traversal – “;
    inorder_traversal(root);
    cout << endl;
    cout << endl;
    
    cout << “8 deleted \n;
    Delete(root, first_delete);
    cout << “Inorder Traversal – “;
    inorder_traversal(root);
    cout << endl;
    cout << endl;
    
    cout << “13 deleted \n;
    Delete(root, second_delete);
    cout << “Inorder Traversal – “;
    inorder_traversal(root);
    cout << endl;
    cout << endl;
    
    cout << “18 deleted \n;
    Delete(root, third_delete);
    cout << “Inorder Traversal – “;
    inorder_traversal(root);
    cout << endl;
    
}

 

Output:

Inorder Traversal - 8 13 14 15 16 18 19 

8 deleted
Inorder Traversal - 13 14 15 16 18 19

13 deleted
Inorder Traversal - 14 15 16 18 19

18 deleted
Inorder Traversal - 14 15 16 19



Time Complexity To Delete Element in Binary Search Tree

Time Complexity

O(n)

Space Complexity

O(h)