Delete A Node In Binary Search Tree In C

In this post, you will learn how to delete a node in a binary search tree using recursion.

To learn deletion of a node in BST first you need to learn about recursion, which is a function calling itself.

How To Delete A Node In Binary Search Tree In C?

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

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

int Min(struct node *root)
{
	struct node *temp = root;
	while(temp->left != NULL){  
	    temp = temp->left;
	}
    return temp->key;
}

struct node *delete(struct node *root, int val)
{   
    if(root == NULL)
        return NULL;
    if(root->key<val)
        root->right = delete(root->right, val);
    else if(root->key>val)
        root->left = delete(root->left, val);    
    else{
        if(root->left==NULL && root->right==NULL){
            free(root);
            return NULL;
        }
        else if(root->left==NULL){
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if(root->right==NULL){
            struct node *temp = root->left;
            free(root);
            return temp;
        }
        else{
            int rightMin = Min(root->right);
            root->key = rightMin;
            root->right = delete(root->right, rightMin);
        }
    }
    return root;
}

struct node *newnode(int val){

    struct node *new = malloc(sizeof(struct node));
    new->key   = val;
    new->left  = NULL;
    new->right = NULL;
    return new;

} 

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

void inorder(struct node *root)
{
    if(root == NULL)
        return;
    inorder(root->left);
    printf("%d ",root->key);
    inorder(root->right);
}

int main(){
    struct node *root = NULL;
    root = insert(root,50);
    root = insert(root,30);
    root = insert(root,20);
    root = insert(root,40);
    root = insert(root,70);
    root = insert(root,60);
    root = insert(root,80);

    int key;
    scanf("%d",&key);
    root = delete(root,key);
    inorder(root);

    return 0;
}

In Inorder traversal we traverse from left-root-right.

Deletion In BST can be possible in three cases:

1. When the root have no child

2. When the root have one NULL value and one root child

3. When the root have two child

Explanation

1. When the root have no child it is very easy to delete by free method, and return the NULL.
2. When the root have one child then we can replace the root by that child by using some temporary variable to store and free the root.
3. Now when we have two child of a root then deleting the root become difficult, For this we have to replace the root with root right child and delete the root child and point it to the NULL.