C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree (BST) — Deletion Operation

Concept Overview

In a Binary Search Tree, deletion means removing a node while maintaining the BST property:

  • Left subtree values < node
  • Right subtree values > node

Cases in BST Deletion

There are three cases to handle when deleting a node from a BST:

Case 1: Node is a Leaf (No Children)

  • Simply remove the node.
  • Example: Delete 20 from this tree:

      50

     /  \

   30    70

  / \    / \

20  40  60  80

→ 20 is removed directly.

Case 2: Node has One Child

  • Replace the node with its child.
  • Example: If 30 has only a left child (say 25), replace 30 with 25.

Case 3: Node has Two Children

  • Find the inorder successor (smallest node in right subtree).
  • Copy its data to the node to be deleted.
  • Delete the inorder successor.

This preserves BST ordering.

 

C Program: Binary Search Tree (BST) — Deletion Operation

BST Deletion (Recursive Implementation)

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 new 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 value node in BST


struct Node* findMin(struct Node* node) {


    struct Node* current = node;


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


        current = current->left;


    return current;


}


 


// Function to delete a node from BST


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


    if (root == NULL)


        return root;


 


    // Recur down the tree


    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: Node with only one child or no child


        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 2: Node with two children


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


 


        // Copy inorder successor's data to this node


        root->data = temp->data;


 


        // Delete inorder successor


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


    }


    return root;


}


 


// Inorder Traversal (for sorted output)


void inorder(struct Node* root) {


    if (root != NULL) {


        inorder(root->left);


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


        inorder(root->right);


    }


}


 


int main() {


    struct Node* root = NULL;


 


    // Insert nodes


    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("Deleting 20 (Leaf Node)\n");


    root = deleteNode(root, 20);


    printf("Inorder after deleting 20: ");


    inorder(root);


    printf("\n");


 


    printf("Deleting 30 (Node with One Child)\n");


    root = deleteNode(root, 30);


    printf("Inorder after deleting 30: ");


    inorder(root);


    printf("\n");


 


    printf("Deleting 50 (Node with Two Children)\n");


    root = deleteNode(root, 50);


    printf("Inorder after deleting 50: ");


    inorder(root);


    printf("\n");


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Deleting 20 (Leaf Node)
Inorder after deleting 20: 30 40 50 60 70 80
Deleting 30 (Node with One Child)
Inorder after deleting 30: 40 50 60 70 80
Deleting 50 (Node with Two Children)
Inorder after deleting 50: 40 60 70 80

Tree Transformations Step-by-Step

Initial BST:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

After Deleting 20 (Leaf):

        50

       /  \

     30    70

      \    / \

      40  60  80

After Deleting 30 (One Child):

        50

       /  \

     40    70

          / \

        60   80

After Deleting 50 (Two Children):

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

        60

       /  \

     40    70

             \

              80

 Final Inorder Traversal: 40 60 70 80

Complexity Analysis

Operation

Average Case

Worst Case (Skewed Tree)

Deletion

O(log n)

O(n)

Search for Successor

O(log n)

O(n)

Space (Recursive)

O(h)

O(n)

Key Points

  • Inorder traversal of a BST always gives sorted output.
  • Inorder successor (minimum in right subtree) is crucial for deleting nodes with two children.
  • BST performance degrades to O(n) if the tree becomes skewed — hence balanced BSTs (like AVL, Red-Black Trees) are used in practice.

 

Previous
Next