How to Delete a Node from BST in C: Syntax and Example

To delete a node from a BST in C, you find the node, then handle three cases: node with no children, one child, or two children. For two children, replace the node with its inorder successor or predecessor, then delete that successor/predecessor node.

Syntax

The deleteNode function takes the root of the BST and the key to delete. It returns the new root after deletion.

• Check if the root is NULL, return NULL if yes.
• Recursively find the node to delete by comparing the key with the current node's value.
• Handle deletion based on the node's children count.

c

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
        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;
        }
        // Node with two children
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Example

This example creates a BST, deletes a node with two children, and prints the inorder traversal before and after deletion.

c

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) return newNode(data);
    if (data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);
    return root;
}

struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;
    while (current && current->left != NULL) current = current->left;
    return current;
}

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 {
        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;
        }
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    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 before deletion: ");
    inorder(root);
    printf("\n");

    root = deleteNode(root, 50);

    printf("Inorder traversal after deleting 50: ");
    inorder(root);
    printf("\n");

    return 0;
}

Output

Inorder traversal before deletion: 20 30 40 50 60 70 80 
Inorder traversal after deleting 50: 20 30 40 60 70 80 

Common Pitfalls

• Not handling the three cases of deletion separately causes errors.
• For nodes with two children, forgetting to replace with inorder successor or predecessor leads to broken BST.
• Not freeing memory after deletion causes memory leaks.
• Incorrect recursion can lose parts of the tree.

c

/* Wrong: Deleting node without handling two children case properly */
struct Node* wrongDelete(struct Node* root, int key) {
    if (root == NULL) return root;
    if (key < root->data) {
        root->left = wrongDelete(root->left, key);
    } else if (key > root->data) {
        root->right = wrongDelete(root->right, key);
    } else {
        free(root); // frees node but does not reconnect children
        return NULL;
    }
    return root;
}

/* Right: Use deleteNode function shown earlier to handle all cases */

Quick Reference

• Find node to delete by comparing keys.
• If node has no children, free and return NULL.
• If node has one child, link parent to child and free node.
• If node has two children, replace with inorder successor (smallest in right subtree), then delete successor.
• Always free memory of deleted node.

Key Takeaways

Deleting from BST requires handling three cases: no child, one child, and two children.

For two children, replace the node with its inorder successor and delete that successor.

Always free the memory of the deleted node to avoid leaks.

Use recursion carefully to maintain BST structure after deletion.

Test deletion with inorder traversal to verify correctness.