This C program demonstrates the essential operations for managing a Binary Search Tree: inserting new elements, deleting elements, and searching for elements in the tree.

Program Explanation

The program is structured into several parts:

• Node Structure: Defines the structure of a BST node.
• Insert Function: Recursively inserts a new node into the BST.
• Search Function: Recursively searches for a value in the BST.
• Delete Function: Recursively removes a node from the BST, ensuring the BST properties are maintained.
• Main Function: Demonstrates the usage of insert, delete, and search operations.

Program Code

// Include necessary headers
#include <stdio.h>
#include <stdlib.h>

// Define the structure for BST nodes
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function to insert a new node into the BST
Node* insert(Node* node, int data) {
    if (node == NULL) return createNode(data);

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);

    return node;
}

// Function to search a node with given data in the BST
Node* search(Node* root, int data) {
    if (root == NULL || root->data == data)
        return root;

    if (data < root->data)
        return search(root->left, data);

    return search(root->right, data);
}

// Function to delete a node from the BST
Node* deleteNode(Node* root, int data) {
    if (root == NULL) return root;

    // Find the node to be deleted
    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        // Node with only one child or no child
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        // Node with two children: Get the inorder successor
        Node* temp = minValueNode(root->right);

        // Copy the inorder successor's content to this node
        root->data = temp->data;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// Function to find the minimum value node
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

// Main function to demonstrate insert, delete, and search operations
int main() {
    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);

    printf("Searching for 40 in BST: %s\\n", search(root, 40) ? "Found" : "Not Found");
    root = deleteNode(root, 20);
    printf("After deleting 20, searching for 20 in BST: %s\\n", search(root, 20) ? "Found" : "Not Found");

    return 0;
}
    

Key Components of the Program:

• Node Structure: Defines each node of the BST containing data and pointers to left and right children.
• createNode Function: Allocates memory and initializes a new node.
• insert Function: Recursively inserts a new node while maintaining BST properties.
• search Function: Searches for a node with given data, returning the node if found, otherwise NULL.
• deleteNode Function: Removes a node with specified data, adjusting the tree to maintain BST properties.
• minValueNode Function: Finds the node with the minimum value in a subtree, used during the delete operation to find the inorder successor.
• Main Function: Demonstrates the usage of insert, delete, and search operations, showing the tree’s behavior after each operation.

This structure ensures clarity and separation of concerns, allowing easy updates and maintenance of each part of the BST’s functionality.