C program that demonstrates Binary Search Tree(BST) traversals, searching, insertion, and deletion.

C program that demonstrates binary search tree (BST) traversal, searching, insertion, and deletion:

#include <stdio.h>

#include <stdlib.h>

// Definition of a node in the BST

struct node {

    int data;

    struct node *left;

    struct node *right;

};

// Function to create a new node

struct node *newNode(int data) {

    struct node temp = (struct node )malloc(sizeof(struct node));

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

// Function to insert a new node with given key in BST

struct node insert(struct node node, int data) {

    // If the tree is empty, return a new node

    if (node == NULL) return newNode(data);

    // Otherwise, recur down the tree

    if (data < node->data)

        node->left = insert(node->left, data);

    else if (data > node->data)

        node->right = insert(node->right, data);

    // Return the (unchanged) node pointer

    return node;

}

// Function to perform InOrder traversal of BST

void inOrder(struct node *root) {

    if (root != NULL) {

        inOrder(root->left);

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

        inOrder(root->right);

    }

}

// Function to perform PostOrder traversal of BST

void postOrder(struct node *root) {

    if (root != NULL) {

        postOrder(root->left);

        postOrder(root->right);

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

    }

}

// Function to perform PreOrder traversal of BST

void preOrder(struct node *root) {

    if (root != NULL) {

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

        preOrder(root->left);

        preOrder(root->right);

    }

}

// Function to search a given key in a given BST

struct node search(struct node root, int key) {

    // Base Cases: root is null or key is present at root

    if (root == NULL || root->data == key)

        return root;

    // Key is greater than root's key

    if (root->data < key)

        return search(root->right, key);

    // Key is smaller than root's key

    return search(root->left, key);

}

// Function to find the minimum value node in a given BST

struct node minValueNode(struct node node) {

    struct node *current = node;

    // Loop down to find the leftmost leaf

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

        current = current->left;

    return current;

}

// Function to delete a node with given key from the BST

struct node deleteNode(struct node root, int key) {

    // Base Case

    if (root == NULL) return root;

    // If the key to be deleted is smaller than the root's key,

    // then it lies in the left subtree

    if (key < root->data)

        root->left = deleteNode(root->left, key);

    // If the key to be deleted is greater than the root's key,

    // then it lies in the right subtree

    else if (key > root->data)

        root->right = deleteNode(root->right, key);

    // If key is the same as root's key, then this is the node

    // to be deleted

    else {

        // 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;

        }

        // Node with two children: Get the inorder successor (smallest

        // in the right subtree)

        struct 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;

}

// Driver program to test above functions

int main() {

    struct node *root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

    printf("Inorder traversal: ");

    inOrder(root);

    printf("\n");

    printf("Postorder traversal: ");

    postOrder(root);

    printf("\n");

    printf("Preorder traversal: ");

    preOrder(root);

    printf("\n");

    int key = 40;

    root = deleteNode(root, key);

    printf("Inorder traversal after deletion of %d: ", key);

    inOrder(root);

    printf("\n");

    return 0;

}

Explanation:

1. Struct Node Definition: Defines a structure for each node in the binary search tree, containing integer data and pointers to the left and right child nodes.

2. newNode() Function: Allocates memory for a new node, initializes its data, and sets both left and right pointers to NULL.

3. Insert() Function: Inserts a new node into the BST according to the rules of a binary search tree: lesser values go to the left subtree, and greater values go to the right subtree.

4. Traversal Functions (inOrder, preOrder, postOrder): These functions perform in-order, pre-order, and post-order traversal of the BST respectively. They recursively traverse the tree, printing the data of each node in the specified order.

5. Search() Function: Searches for a given key in the BST. It returns a pointer to the node containing the key if found, otherwise NULL.

6. minValueNode() Function: Finds the node with the minimum value in the given BST. It traverses to the leftmost leaf node to find the minimum value.

7. deleteNode() Function: Deletes a node with a given key from the BST. It first searches for the node to be deleted using search() function. Then, it handles cases where the node has either zero, one, or two children accordingly.

8. Main() Function: Demonstrates the usage of the implemented functions by creating a BST, inserting elements, performing traversals, and deleting a node.