C Programming Data Structures Insertion Deletion In Bst Complete Guide

Binary Search Tree (BST) Basics

A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.

Node Structure:

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

Insertion in BST

To insert a new node into a BST, we need to maintain the properties of BST. Here is how it can be done:

Step-by-Step Instructions:

1. Define the Node Structure: As shown above.
2. Create a Function to Allocate Memory for a New Node:
   • This function will create a new node with the provided data and return a pointer to the newly created node.
   • Initialize its left and right pointers to NULL.
3. Create a Function to Insert Nodes into the BST:
   • It should take the root of the tree and the data of the new node as input arguments.
   • If the root (key) is NULL, this case denotes that we have reached a leaf node. Create a new node here and return its address.
   • Otherwise, compare the new element with the current root element.
   • If the new element is less than the current root element, recursively insert the new element in the left sub-tree.
   • If the new element is more than the current root element, recursively insert the new element in right sub-tree.

Complete Example Code:

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

// Define the Node structure
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 = NULL;
    temp->right = NULL;
    return temp;
}

// Function to insert nodes into the BST
struct Node* insert(struct Node* root, int data) {
    if (root == NULL)
        return newNode(data);

    // Recursively insert in the right or left subtree
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);

    return root;
}

// Helper function to print the BST elements (inorder traversal)
void inorderTraverse(struct Node* root) {
    if (root != NULL) {
        inorderTraverse(root->left);
        printf("%d ", root->data);
        inorderTraverse(root->right);
    }
}

// Main function
int main() {
    struct Node* root = NULL;
    root = insert(root, 45);
    insert(root, 35);
    insert(root, 70);
    insert(root, 50);
    insert(root, 90);
    insert(root, 10);
    insert(root, 60);

    printf("Inorder Traversal of the BST: ");
    inorderTraverse(root);
    printf("\n");

    return 0;
}

Deletion in BST

Deletion in a Binary Search Tree can be a bit complex compared to insertion. When deleting a node, three possibilities arise:

1. The node to be deleted is a leaf node.
2. The node to be deleted has only one child.
3. The node to be deleted has two children (both sub-trees).

Step-by-Step Instructions:

1. Define a Min Value Node Finder Function: To find the minimum value node in a tree.
   • This minimum value node is useful when the deleted node has two children.
2. Create a Function to Delete Nodes from the BST:
   • It should take the root of the tree and the data to be deleted as input arguments.
   • First, search for the node you want to delete.
   • Now, there are four cases:
     • If the node to be deleted does not exist, just return the original root.
     • If the node to be deleted is smaller than the root, then recurse on the left subtree.
     • If the node to be deleted is greater than the root, then recurse on the right subtree.
     • If the node to be deleted is the root itself:
       • Case 1: The node has no children - it is a leaf node. Simply set the root to NULL.
       • Case 2: One child - Copy the child to the root and delete the child.
       • Case 3: Two children - Find the smallest element in the right subtree (this is an inorder successor), copy its value in the root node, and then delete the inorder successor.

Complete Example Code:

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

// Define the Node structure
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 = NULL;
    temp->right = NULL;
    return temp;
}

// Function to insert nodes into the BST
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 if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

// Helper function to print the BST elements (inorder traversal)
void inorderTraverse(struct Node* root) {
    if (root != NULL) {
        inorderTraverse(root->left);
        printf("%d ", root->data);
        inorderTraverse(root->right);
    }
}

// Function to find the minimum value node in a BST
struct Node* findMinNode(struct Node* node) {
    struct Node* current = node;

    // Traverse the left subtree to find the leftmost leaf
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

// Function to delete a node from the BST
struct Node* deleteNode(struct Node* root, int data) {
    // Base case: Empty tree or node not found
    if (root == NULL)
        return root;

    // Recursively search for the node to delete
    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    // Node to be deleted found
    else {
        // **CASE 1:** Node with only one child (or no children)
        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;
        }

        // **CASE 2:** Node with two children
        // Get the inorder successor
        struct Node* temp = findMinNode(root->right);
        root->data = temp->data;  // Copy inorder successor's content to this node
        root->right = deleteNode(root->right, temp->data);  // Delete inorder successor
    }
    return root;
}

// Main function
int main() {
    struct Node* root = NULL;
    root = insert(root, 45);
    insert(root, 35);
    insert(root, 70);
    insert(root, 50);
    insert(root, 90);
    insert(root, 10);
    insert(root, 60);

    printf("Inorder Traversal of the BST before deletion: ");
    inorderTraverse(root);
    printf("\n");

    root = deleteNode(root, 50);
    printf("Inorder Traversal of the BST after deleting 50: ");
    inorderTraverse(root);
    printf("\n");

    root = deleteNode(root, 90);
    printf("Inorder Traversal of the BST after deleting 90: ");
    inorderTraverse(root);
    printf("\n");

    root = deleteNode(root, 60);
    printf("Inorder Traversal of the BST after deleting 60: ");
    inorderTraverse(root);
    printf("\n");

    return 0;
}

Running the Code

Compile and run the insertion-deletion BST example program. You will get the following output:

Inorder Traversal of the BST before deletion: 10 35 45 50 60 70 90 
Inorder Traversal of the BST after deleting 50: 10 35 45 60 70 90 
Inorder Traversal of the BST after deleting 90: 10 35 45 60 70 
Inorder Traversal of the BST after deleting 60: 10 35 45 70 

This output confirms that:

• The nodes are correctly inserted into the BST maintaining the BST property.
• The specified nodes are correctly deleted and the resulting trees still maintain the BST properties.