Binary Search Tree | Deletion

Deletion of a node in a BST can be more complicated task than searching or inserting a node.

Suppose we want to delete a node P

1> If P is a leaf node i.e. it has no children, then we will just replace P by null.

          8                               8
        /   \          delete(9)        /   \
       3    10         ---------->     3    10
      / \   /                         / \
     1   5 9                         1   5

2> If P has only one child, then we will place the child to P's place.

          8                               8
        /   \          delete(10)       /   \
       3    10         ---------->     3     9
      / \   /                         / \
     1   5 9                         1   5

3>If P has two children, then we will identify P's successor. Call it Q. The successor Q either is a leaf or has only the right child. We will replace P by Q and delete Q.(if it has right child then follow method 2)

         8                              9
       /   \          delete(8)       /   \
      3    10         ---------->    3    10
     / \   /                        / \
    1   5 9                        1   5

C Program

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

typedef struct BST
{
   struct BST *lc, *rc;
   int data;
}BST;

BST *insertNode(BST *T,int item)
{
    BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found)
    {
        //Keeping track of the previous node...
        prev = curr; 
        // If item already exists...
        if(curr->data == item) 
        {
            found = 1;
            printf("\nItem %d Already Exists In The BST.\n",item);
        }
        else if(curr->data > item) {
            curr = curr->lc;
        }
        else {
            curr = curr->rc;
        }
    }
    //Creating a new node...
    temp = (BST*)malloc(sizeof(BST));
    temp->data = item;
    temp->lc = NULL;
    temp->rc = NULL;
    //Only for first node or time...
    if(T == NULL)
        T = temp;
    else if(item > prev->data)
        prev->rc = temp;
    else
        prev->lc = temp;
    return T;
}

void inorder(BST *t)
{
    if(t != NULL) 
    {
        inorder(t->lc);
        printf("%d ",t->data);
        inorder(t->rc);
    }
}

BST *deleteNode(BST *root,int item)
{
    BST *curr = root, *temp = NULL, *parent;
    while(curr != NULL)
    {
        if(curr->data == item)
            break;
        parent  = curr;
        if(item > curr->data)
            curr = curr->rc;
        else
            curr = curr->lc;
    }
    if(curr == NULL)
    {
        printf("\nDelete Request Failed. Value Not Exists.");
        return root;
    }
    else if(curr->lc == NULL && curr->rc == NULL) // Leaf node (case 1)
    {
        if(parent == NULL)
            root = NULL;
        else if(parent->lc == curr)
            parent->lc = NULL;
        else
            parent->rc = NULL;
        return root;
    }
    else if(curr->lc != NULL && curr->rc == NULL) // Only one child (case 2)
    {
        if (root->data == curr->data) 
            root = curr->lc;
        else if(parent->lc == curr)
            parent->lc = curr->lc;
        else
            parent->rc = curr->lc;
        free(curr);
        return root;
    }
    else if(curr->rc != NULL && curr->lc == NULL) // Only one child (case 2)
    {
        if (root->data == curr->data) 
            root = curr->rc;
        else if(parent->lc == curr)
            parent->lc = curr->rc;
        else
            parent->rc = curr->rc;
        free(curr);
        return root;
    }
    else // both child (case 3)
    {
        parent = curr;
        temp = curr->rc;
        while(temp->lc != NULL)
        {
            parent = temp;
            temp = temp->lc;
        }
        curr->data = temp->data;
        if(curr == parent)
            curr->rc = temp->rc;
        else
            parent->lc = temp->rc;      
        free(temp);
        return root;
    }
}

int main()
{
    BST *T = NULL;
    int value;
    T = insertNode(T, 8);
    insertNode(T, 3);
    insertNode(T, 10);
    insertNode(T, 1);
    insertNode(T, 5);
    insertNode(T, 9);
    
    printf("Full Tree: ");
    inorder(T);
    printf("\nAFter Deleting 9(leaf node): ");
    T = deleteNode(T, 9);
    inorder(T);
    printf("\nAFter Deleting 10(node w/ one child): ");
    T = deleteNode(T, 10);
    inorder(T);
    printf("\nAFter Deleting 8(root node): ");
    T = deleteNode(T, 8);
    inorder(T);
    printf("\nAFter Deleting 3(full node): ");
    T = deleteNode(T, 3);
    inorder(T);
    return 0;
}

Output

Full Tree: 1 3 5 8 9 10
AFter Deleting 9(leaf node): 1 3 5 8 10
AFter Deleting 10(node w/ one child): 1 3 5 8
AFter Deleting 8(root node): 1 3 5
AFter Deleting 3(full node): 1 5
--------------------------------
Process exited after 0.4866 seconds with return value 0
Press any key to continue . . .