C Program to Implement Binary Search Tree

1. Introduction

A Binary Search Tree (BST) is a tree in which all the nodes follow the left child < parent < right child property. This property ensures that the left subtree contains elements less than the node, and the right subtree contains elements greater than the node. BSTs are widely used due to their efficiency in many operations, like search, insert, and delete.

2. Program Overview

In this program, we will:

1. Define a node structure for our BST.

2. Implement the following BST operations:

- Insertion: To add an element to the BST.

- Deletion: To remove an element from the BST.

- Search: To check if an element exists in the BST.

- Inorder Traversal: To display the BST in ascending order.

3. Code Program

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

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

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

// Function to insert a node into BST
Node* insert(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 node with minimum value
Node* minValueNode(Node* root) {
    Node* current = root;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

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

    // Recursive calls for ancestors of the node to be deleted
    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else {
        // Node with 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
        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// Function to perform in-order traversal
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

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("Inorder traversal: ");
    inorder(root);
    printf("\n");

    printf("Delete 20: ");
    root = deleteNode(root, 20);
    inorder(root);
    printf("\n");

    printf("Delete 30: ");
    root = deleteNode(root, 30);
    inorder(root);
    printf("\n");

    printf("Delete 50: ");
    root = deleteNode(root, 50);
    inorder(root);
    printf("\n");

    return 0;
}

Output:

Inorder traversal: 20 30 40 50 60 70 80
Delete 20: 30 40 50 60 70 80
Delete 30: 40 50 60 70 80
Delete 50: 40 60 70 80

4. Step By Step Explanation

1. We begin by defining a node structure for our BST. Each node contains an integer data, a pointer to the left child, and a pointer to the right child.

2. The insert function adds a new node to the BST while maintaining its properties.

3. The minValueNode function returns the node with the smallest value greater than the passed node.

4. The deleteNode function removes a node from the BST and adjusts the tree to preserve the BST property.

5. The inorder function traverses the BST in ascending order.

6. In the main function, we demonstrate the insertion of several nodes, in-order traversal, and deletion of nodes followed by traversal to show the updated BST.