Binary Search Trees: Deletion of a node in a BST

Problem Statement:

You are given BST root node and a key value.

You need to delete that node from BST.

Solution

There are few cases to be considered.

1. If the key is equal to the leaf node, then we can delete directly.

2. If the node is having children, then we need to choose an inorder successor node and then delete the node.

Example:

1) If it is a leaf node, delete directly

              5                              5
           /     \         delete(2)       /   \
          3       7        --------->    3      7 
         /  \    /  \                     \    /  \ 
        2   4   6    8                    4   6    8

2) If the node to be deleted has only one child then copy the child to the node and delete the child

              5                             5
           /     \         delete(3)      /   \
          3       7        --------->    4     7 
            \                              
            4                              

3) If the node to be deleted has 2 children then find its inorder successor of the node, then copy the contents of inorder successor to the node and delete the inorder successor of that node.


              5                             6
           /     \         delete(5)      /   \
          4       7       --------->    4     7 
                 /  \                            \ 
                 6   8                            8

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <unordered_map> 

using namespace std;

struct Node
{
    int data;
    Node *left;
    Node *right;
};

//global root declaration
Node *root;

Node* insert(int num, Node* root)
{
    if(root == NULL)
    {
        root = new Node;
        root->data = num;
        root->left = root->right = NULL;
    }
    else if(num < root->data)
        root->left = insert(num, root->left);

    else if(num > root->data)
        root->right = insert(num, root->right);
    return root;
}

void inorder(Node *root)
{
    if(root == NULL)
        return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

Node* findMin(Node* root)
{
    if(root == NULL)
        return NULL;
    else if(root->left == NULL)
        return root;
    else
        return findMin(root->left);
}


Node* remove(Node* node, int key)
{
   Node* temp;
    if(node == NULL)
        return NULL;
    else if(key < node->data)
        node->left = remove(node->left, key);
    else if(key > node->data)
        node->right = remove(node->right, key);
    else if(node->left && node->right)
    {
        temp = findMin(node->right);
        node->data = temp->data;
        node->right = remove(node->right, node->data);
    }
    else
    {
        temp = node;
        if(node->left == NULL)
            node = node->right;
        else if(node->right == NULL)
            node = node->left;
        delete temp;
    }

    return node;
}

int main()
{
    root = insert(10, root);
    root = insert(30, root);
    root = insert(20, root);
    root = insert(50, root);
    root = insert(60, root);
    root = insert(25, root);
    root = insert(15, root);

    cout<<"\nThe inorder traversal before removing 60 "<<endl;
    inorder(root); 

    remove(root, 60);

    cout<<"\nThe inorder traversal before removing 60 "<<endl;
    inorder(root); 

   return 0;
   
}

Output:

The inorder traversal before removing 60
10 15 20 25 30 50 60
The inorder traversal before removing 60
10 15 20 25 30 50

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *