BST Operations: Insert, Delete, and Search in C++

Introduction

A Binary Search Tree (BST) is a data structure in which each node follows the rule:

• All nodes in the left subtree of a node contain values less than the node’s value.
• All nodes in the right subtree contain values greater than the node’s value.

In this guide, we will implement three fundamental operations for a BST in C++:

• Insert a node
• Delete a node
• Search for a node

Program Structure

The program will follow these steps:

1. Define a TreeNode structure to represent nodes in the BST.
2. Implement the insert function to add a new node to the BST.
3. Implement the deleteNode function to remove a node from the BST.
4. Implement the search function to find a node in the BST.
5. Helper functions for traversing and printing the tree (for testing purposes).

Code Implementation

// C++ program to implement Insert, Delete, and Search in a Binary Search Tree

#include <iostream>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function to insert a node in the BST
TreeNode* insert(TreeNode* root, int key) {
    // If the tree is empty, create a new node
    if (root == NULL)
        return new TreeNode(key);

    // If the key is smaller, insert in the left subtree
    if (key < root->val)
        root->left = insert(root->left, key);
    // If the key is larger, insert in the right subtree
    else if (key > root->val)
        root->right = insert(root->right, key);

    // Return the unchanged node pointer
    return root;
}

// Helper function to find the minimum value node in the BST (used during deletion)
TreeNode* findMin(TreeNode* root) {
    while (root && root->left != NULL)
        root = root->left;
    return root;
}

// Function to delete a node from the BST
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return root;  // Base case: if tree is empty

    // If the key is smaller, delete from the left subtree
    if (key < root->val)
        root->left = deleteNode(root->left, key);
    // If the key is larger, delete from the right subtree
    else if (key > root->val)
        root->right = deleteNode(root->right, key);
    else {
        // Node with only one child or no child
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }

        // Node with two children: get the inorder successor (smallest in the right subtree)
        TreeNode* temp = findMin(root->right);

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

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

    return root;
}

// Function to search for a node in the BST
bool search(TreeNode* root, int key) {
    if (root == NULL) return false;  // Base case: if tree is empty

    // If the key is found, return true
    if (root->val == key)
        return true;
    
    // Recursively search in the left or right subtree
    if (key < root->val)
        return search(root->left, key);
    else
        return search(root->right, key);
}

// Helper function to perform in-order traversal and print the BST (for testing purposes)
void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return;

    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

int main() {
    /* Sample Binary Search Tree (BST):
              50
            /    \
          30      70
         /  \    /  \
       20   40  60   80
    */

    // Create an empty BST
    TreeNode* root = NULL;

    // Insert nodes into the BST
    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);

    // Perform in-order traversal to display the BST
    cout << "In-order Traversal of the BST: ";
    inOrderTraversal(root);
    cout << endl;

    // Search for a key in the BST
    int key = 40;
    if (search(root, key))
        cout << "Key " << key << " found in the BST." << endl;
    else
        cout << "Key " << key << " not found in the BST." << endl;

    // Delete a node from the BST
    root = deleteNode(root, 40);

    // Perform in-order traversal after deletion
    cout << "In-order Traversal of the BST after deleting 40: ";
    inOrderTraversal(root);
    cout << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary search tree. Each node stores a value val and pointers to its left and right children.
2. insert function: This function inserts a new node into the BST by recursively finding the correct position based on the value of the key (left for smaller, right for larger).
3. deleteNode function: This function removes a node from the BST. It handles three cases:
   • Node has no children (leaf node).
   • Node has one child (either left or right).
   • Node has two children: We replace the node with its inorder successor (the smallest node in the right subtree) and recursively delete the successor.
4. search function: This function searches for a node in the BST by recursively checking whether the key matches the current node’s value, and if not, proceeding to either the left or right subtree based on the key’s value.
5. inOrderTraversal function: This function prints the elements of the BST in sorted order by performing an in-order traversal (left subtree, root, right subtree).

How the Algorithm Works

The insert function ensures that the BST properties are maintained as new nodes are added. The delete function maintains the structure of the BST by properly handling nodes with zero, one, or two children. The search function efficiently finds a node by exploiting the BST’s property that values in the left subtree are smaller and values in the right subtree are larger.

Sample Output

If you run the above program with the provided sample tree, the output will be:

In-order Traversal of the BST: 20 30 40 50 60 70 80 
Key 40 found in the BST.
In-order Traversal of the BST after deleting 40: 20 30 50 60 70 80 

Conclusion

In this program, we implemented three fundamental operations (insert, delete, and search) for a Binary Search Tree in C++. The time complexity of each operation is O(h), where h is the height of the tree. For a balanced tree, this is O(log N), while for a skewed tree, it can be O(N). Understanding these operations is crucial for working with BSTs in various applications such as searching, sorting, and managing dynamic datasets.