C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree — Deleting a Node from a Binary Search Tree

Deleting a Node from a BST

Deletion requires careful handling because we must preserve the BST property after removing a node.

Binary Search Tree — Deletion Operation

Concept Overview

When deleting a node from a BST, there are three possible cases:

  1. Case 1: Node to be deleted is a leaf node (no children).
    → Simply remove it.
  2. Case 2: Node to be deleted has one child.
    → Replace it with its child.
  3. Case 3: Node to be deleted has two children.
    → Find its inorder successor (smallest node in the right subtree),
    replace the node’s value with the successor’s value,
    and then delete the successor node.

Algorithm Summary

struct Node* deleteNode(struct Node* root, int key) {

    if (root == NULL)

        return root;

 

    // Step 1: Search for the node

    if (key < root->data)

        root->left = deleteNode(root->left, key);

    else if (key > root->data)

        root->right = deleteNode(root->right, key);

    else {

        // Step 2: Node found

 

        // Case 1: No child

        if (root->left == NULL && root->right == NULL) {

            free(root);

            return NULL;

        }

 

        // Case 2: One child

        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;

        }

 

        // Case 3: Two children

        else {

            struct Node* temp = findMin(root->right);

            root->data = temp->data;

            root->right = deleteNode(root->right, temp->data);

        }

    }

    return root;

}

 

C Program: Binary Search Tree - Deletion Operation

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for BST Node


struct Node {


    int data;


    struct Node *left, *right;


};


 


// Function to create a new node


struct Node* createNode(int value) {


    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));


    newNode->data = value;


    newNode->left = newNode->right = NULL;


    return newNode;


}


 


// Function to insert a node in BST


struct Node* insert(struct Node* root, int value) {


    if (root == NULL)


        return createNode(value);


 


    if (value < root->data)


        root->left = insert(root->left, value);


    else if (value > root->data)


        root->right = insert(root->right, value);


 


    return root;


}


 


// Function to find the minimum node (used in deletion)


struct Node* findMin(struct Node* root) {


    while (root && root->left != NULL)


        root = root->left;


    return root;


}


 


// Function to delete a node from BST


struct Node* deleteNode(struct Node* root, int key) {


    if (root == NULL)


        return root;


 


    if (key < root->data)


        root->left = deleteNode(root->left, key);


    else if (key > root->data)


        root->right = deleteNode(root->right, key);


    else {


        // Node found


 


        // Case 1: No child


        if (root->left == NULL && root->right == NULL) {


            free(root);


            return NULL;


        }


 


        // Case 2: One child


        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;


        }


 


        // Case 3: Two children


        else {


            struct Node* temp = findMin(root->right);


            root->data = temp->data;


            root->right = deleteNode(root->right, temp->data);


        }


    }


 


    return root;


}


 


// Inorder traversal for verification


void inorder(struct Node* root) {


    if (root != NULL) {


        inorder(root->left);


        printf("%d ", root->data);


        inorder(root->right);


    }


}


 


int main() {


    struct Node* root = NULL;


    int key;


 


    // Construct BST


    root = insert(root, 50);


    root = insert(root, 30);


    root = insert(root, 70);


    root = insert(root, 20);


    root = insert(root, 40);


    root = insert(root, 60);


    root = insert(root, 80);


 


    printf("Inorder Traversal of BST: ");


    inorder(root);


    printf("\n");


 


    printf("Enter element to delete: ");


    scanf("%d", &key);


 


    root = deleteNode(root, key);


 


    printf("Inorder Traversal after Deletion: ");


    inorder(root);


    printf("\n");


 


    return 0;


}

Output

 
Example 1 – Delete a leaf node
Enter element to delete: 20
Inorder Traversal after Deletion: 30 40 50 60 70 80

Example 2 – Delete a node with one child
Enter element to delete: 30
Inorder Traversal after Deletion: 40 50 60 70 80

Example 3 – Delete a node with two children
Enter element to delete: 50
Inorder Traversal after Deletion: 40 60 70 80

Visualization Example

Before deletion:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

Delete 50 (two children):

  • Inorder successor → 60
  • Replace 50 → 60
  • Delete original 60 node

After deletion:

        60

       /  \

     30    70

    / \      \

  20  40     80

Complexity Analysis

Operation

Time Complexity

Space Complexity

Delete

O(h)

O(h) (recursive)

Where h = height of the tree
→ O(log n) for a balanced tree
→ O(n) for a skewed tree

Key Points

  • BST deletion handles three distinct cases (no child, one child, two children).
  • Inorder successor is the smallest node in the right subtree.
  • After deletion, BST property remains intact.
  • Deletion is the most complex BST operation — crucial for mastering tree algorithms.

 

Previous
Next