{"id":659,"date":"2024-10-10T13:41:42","date_gmt":"2024-10-10T08:11:42","guid":{"rendered":"https:\/\/codexplained.in\/?p=659"},"modified":"2025-11-24T15:57:40","modified_gmt":"2025-11-24T10:27:40","slug":"delete-node-in-binary-search-tree","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=659","title":{"rendered":"Delete Node in Binary Search Tree"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Structure for a node in the BST\nstruct Node {\n    int data;\n    struct Node* left;\n    struct Node* right;\n};\n\n\/\/ Function to create a new node\nstruct Node* createNode(int data) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->data = data;\n    newNode->left = newNode->right = NULL;\n    return newNode;\n}\n\n\/\/ Function to insert a new node in the BST\nstruct Node* insert(struct Node* root, int data) {\n    if (root == NULL) {\n        return createNode(data);\n    }\n\n    if (data < root->data) {\n        root->left = insert(root->left, data);\n    } else if (data > root->data) {\n        root->right = insert(root->right, data);\n    }\n\n    return root;\n}\n\n\/\/ Function to find the minimum value node in the right subtree\nstruct Node* findMin(struct Node* root) {\n    while (root->left != NULL) {\n        root = root->left;\n    }\n    return root;\n}\n\n\/\/ Function to delete a node in the BST\nstruct Node* deleteNode(struct Node* root, int data) {\n    if (root == NULL) {\n        return root;\n    }\n\n    \/\/ Find the node to be deleted\n    if (data < root->data) {\n        root->left = deleteNode(root->left, data);\n    } else if (data > root->data) {\n        root->right = deleteNode(root->right, data);\n    } else {\n        \/\/ Node found: let's handle the three cases\n\n        \/\/ Case 1: No child\n        if (root->left == NULL && root->right == NULL) {\n            free(root);\n            return NULL;\n        }\n        \n        \/\/ Case 2: One child (right)\n        else if (root->left == NULL) {\n            struct Node* temp = root->right;\n            free(root);\n            return temp;\n        }\n\n        \/\/ Case 2: One child (left)\n        else if (root->right == NULL) {\n            struct Node* temp = root->left;\n            free(root);\n            return temp;\n        }\n\n        \/\/ Case 3: Two children\n        struct Node* temp = findMin(root->right);\n        root->data = temp->data;\n        root->right = deleteNode(root->right, temp->data);\n    }\n    return root;\n}\n\n\/\/ Function to perform inorder traversal of the BST\nvoid inorder(struct Node* root) {\n    if (root != NULL) {\n        inorder(root->left);\n        printf("%d ", root->data);\n        inorder(root->right);\n    }\n}\n\nint main() {\n    struct Node* root = NULL;\n\n    \/\/ Insert nodes into the BST\n    root = insert(root, 50);\n    root = insert(root, 30);\n    root = insert(root, 20);\n    root = insert(root, 40);\n    root = insert(root, 70);\n    root = insert(root, 60);\n    root = insert(root, 80);\n\n    printf("Inorder traversal before deletion: ");\n    inorder(root);\n    printf("\\n");\n\n    \/\/ Deleting nodes\n    root = deleteNode(root, 20); \/\/ Deleting a leaf node\n    printf("Inorder traversal after deleting 20: ");\n    inorder(root);\n    printf("\\n");\n\n    root = deleteNode(root, 30); \/\/ Deleting a node with one child\n    printf("Inorder traversal after deleting 30: ");\n    inorder(root);\n    printf("\\n");\n\n    root = deleteNode(root, 50); \/\/ Deleting a node with two children\n    printf("Inorder traversal after deleting 50: ");\n    inorder(root);\n    printf("\\n");\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation:<\/h3>\n\n\n\n
    \n
  1. Node Structure<\/strong>:\n
      \n
    • We define a Node<\/code> structure that holds an integer data<\/code>, a pointer to the left child, and a pointer to the right child.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • createNode<\/strong>:\n
        \n
      • Creates a new node with the given value, setting its left and right pointers to NULL<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • insert<\/strong>:\n
          \n
        • Inserts a new node into the BST. If the tree is empty, it creates the root node.<\/li>\n\n\n\n
        • Otherwise, it compares the data with the current node and inserts it into the left or right subtree accordingly.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • findMin<\/strong>:\n
            \n
          • Finds the node with the minimum value in a subtree, which is used to find the inorder successor during deletion.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • deleteNode<\/strong>:\n
              \n
            • Recursively locates the node to be deleted.<\/li>\n\n\n\n
            • Handles the three cases of deletion:\n
                \n
              • For a leaf node, it frees the node.<\/li>\n\n\n\n
              • For a node with one child, it replaces the node with its child.<\/li>\n\n\n\n
              • For a node with two children, it finds the inorder successor, replaces the node\u2019s value with that of the successor, and deletes the successor.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • inorder<\/strong>:\n
                  \n
                • Prints the inorder traversal of the tree, which outputs the BST nodes in a sorted order.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • main<\/strong>:\n
                    \n
                  • Demonstrates the insertion of nodes, deletion of specific nodes, and prints the inorder traversal before and after each deletion.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                    Output:<\/p>\n\n\n\n
                    Inorder traversal before deletion: 20 30 40 50 60 70 80 \nInorder traversal after deleting 20: 30 40 50 60 70 80 \nInorder traversal after deleting 30: 40 50 60 70 80 \nInorder traversal after deleting 50: 40 60 70 80 \n<\/code><\/pre>\n\n\n\n
                    Explanation of the Output:<\/h3>\n\n\n\n
                      \n
                    • Initially, the BST has nodes 20<\/code>, 30<\/code>, 40<\/code>, 50<\/code>, 60<\/code>, 70<\/code>, and 80<\/code>.<\/li>\n\n\n\n
                    • After deleting 20<\/code> (a leaf), it’s removed directly.<\/li>\n\n\n\n
                    • Deleting 30<\/code> (which has one child, 40<\/code>), results in 40<\/code> taking its place.<\/li>\n\n\n\n
                    • Deleting 50<\/code> (which has two children) involves replacing 50<\/code> with its inorder successor 60<\/code>, then removing 60<\/code>.<\/li>\n<\/ul>\n