Deletion in Binary Search Tree

To delete the given node from the binary search tree(BST), we should follow the below rules.




1.Leaf Node

If the node is leaf (both left and right will be NULL), remove the node directly and free its memory.

Example

  100                              100
  / \                              / \
50  200         delete(300)       50  200
    / \                               /
  150  300                           150



2.Node with Right Child

If the node has only right child (left will be NULL), make the node points to the right node and free the node.

Example

  100                              100
  / \                              / \
50  200         delete(200)       50 300
      \
      300



3.Node with Left Child

If the node has only left child (right will be NULL), make the node points to the left node and free the node.

Example

  100                              100
  / \                              / \
50  200         delete(200)       50 150
    /
  150



4.Node has both left and right child

If the node has both left and right child,

1.find the smallest node in the right subtree. say min

2.make node->data = min

3.Again delete the min node.

Example

                                              (step 2)           (step 3)
  100                                           100                 100
  / \                                           / \                 / \
50  200         delete(200)                    50  300             50  300
    / \         (right subtree min = 300)          / \                 /
  150  300      (step 1)                          150 300             150



Remove function with algorithm explanation

struct node *removeNode(struct node *root, int val)
{
    /*
     * If the node becomes NULL, it will return NULL
     * Two possible ways which can trigger this case
     * 1. If we send the empty tree. i.e root == NULL
     * 2. If the given node is not present in the tree.
     */
    if(root == NULL)
        return NULL;
    /*
     * If root->key < val. val must be present in the right subtree
     * So, call the above remove function with root->right
     */
    if(root->key < val)
        root->right = removeNode(root->right,val);
    /*
     * if root->key > val. val must be present in the left subtree
     * So, call the above function with root->left
     */
    else if(root->key > val)
        root->left = removeNode(root->left,val);
    /*
     * This part will be executed only if the root->key == val
     * The actual removal starts from here
     */
    else
    {
        /*
         * Case 1: Leaf node. Both left and right reference is NULL
         * replace the node with NULL by returning NULL to the calling pointer.
         * free the node
         */
        if(root->left == NULL && root->right == NULL)
        {
            free(root);
            return NULL;
        }
        /*
         * Case 2: Node has right child.
         * replace the root node with root->right and free the right node
         */
        else if(root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        /*
         * Case 3: Node has left child.
         * replace the node with root->left and free the left node
         */
        else if(root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }
        /*
         * Case 4: Node has both left and right children.
         * Find the min value in the right subtree
         * replace node value with min.
         * And again call the remove function to delete the node which has the min value.
         * Since we find the min value from the right subtree call the remove function with root->right.
         */
        else
        {
            int rightMin = getRightMin(root->right);
            root->key = rightMin;
            root->right = removeNode(root->right,rightMin);
        }

    }

    //return the actual root's address
    return root;
}



Implementation of Binary Search Tree Deletion (Recursive)

/*
 * Program  : Binary Search Tree Deletion
 * Language : C
 */

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int key;
    struct node *left;
    struct node *right;
};

struct node *getNewNode(int val)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->key   = val;
    newNode->left  = NULL;
    newNode->right = NULL;

    return newNode;
}

struct node *insert(struct node *root, int val)
{
    if(root == NULL)
        return getNewNode(val);
    if(root->key < val)
        root->right = insert(root->right,val);
    else if(root->key > val)
        root->left = insert(root->left,val);

    return root;
}

int getRightMin(struct node *root)
{
    struct node *temp = root;

    //min value should be present in the left most node.
    while(temp->left != NULL){ temp = temp->left;}

    return temp->key;
}

struct node *removeNode(struct node *root, int val)
{
    /*
     * If the node becomes NULL, it will return NULL
     * Two possible ways which can trigger this case
     * 1. If we send the empty tree. i.e root == NULL
     * 2. If the given node is not present in the tree.
     */
    if(root == NULL)
        return NULL;
    /*
     * If root->key < val. val must be present in the right subtree
     * So, call the above remove function with root->right
     */
    if(root->key < val)
        root->right = removeNode(root->right,val);
    /*
     * if root->key > val. val must be present in the left subtree
     * So, call the above function with root->left
     */
    else if(root->key > val)
        root->left = removeNode(root->left,val);
    /*
     * This part will be executed only if the root->key == val
     * The actual removal starts from here
     */
    else
    {
        /*
         * Case 1: Leaf node. Both left and right reference is NULL
         * replace the node with NULL by returning NULL to the calling pointer.
         * free the node
         */
        if(root->left == NULL && root->right == NULL)
        {
            free(root);
            return NULL;
        }
        /*
         * Case 2: Node has right child.
         * replace the root node with root->right and free the right node
         */
        else if(root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        /*
         * Case 3: Node has left child.
         * replace the node with root->left and free the left node
         */
        else if(root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }
        /*
         * Case 4: Node has both left and right children.
         * Find the min value in the right subtree
         * replace node value with min.
         * And again call the remove function to delete the node which has the min value.
         * Since we find the min value from the right subtree call the remove function with root->right.
         */
        else
        {
            int rightMin = getRightMin(root->right);
            root->key = rightMin;
            root->right = removeNode(root->right,rightMin);
        }

    }

    //return the actual root's address
    return root;
}

/*
 * it will print the tree in ascending order
 */
void inorder(struct node *root)
{
    if(root == NULL)
        return;
    inorder(root->left);
    printf("%d ",root->key);
    inorder(root->right);
}

int main()
{
    /*
         100
         / \
        50  200
            /  \
           150  300
     */
    struct node *root = NULL;
    root = insert(root,100);
    root = insert(root,50);
    root = insert(root,200);
    root = insert(root,150);
    root = insert(root,300);

    printf("Initial tree :\t");
    inorder(root);
    printf("\n");

    /* remove leaf node 300
         100
         / \
        50  200
            /
           150
     */
    root = removeNode(root,300);
    printf("After deletion of 300, the new tree :\t");
    inorder(root);
    printf("\n");

    /* remove root node 100
         150
         / \
        50  200
     */
    root = removeNode(root,100);
    printf("After deletion of 100, the new tree :\t");
    inorder(root);
    printf("\n");

    return 0;
}