C Program to Implement Binary Search Tree (BST)

Introduction

A Binary Search Tree (BST) is a binary tree data structure where each node has a key, and the key of the left child is less than the key of the parent node, while the key of the right child is greater than the key of the parent node. This property makes BSTs useful for fast lookup, insertion, and deletion operations, all of which can be done in O(log n) time on average.

Example:

Operations: Insert elements [20, 10, 30, 5, 15, 25, 35], search for 15, and delete 10.
Expected Structure: The tree after these operations will still satisfy the BST properties.

Problem Statement

Create a C program that:

Implements the basic operations of a Binary Search Tree: insertion, searching, and deletion.
Performs an in-order traversal to display the elements of the BST in sorted order.

Solution Steps

Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output and memory allocation functions.
Define the Structure for a Tree Node: Each node will contain a key and pointers to its left and right children.
Implement the BST Operations:

Insert: Insert a new node into the BST.
Search: Search for a key in the BST.
Delete: Delete a node from the BST.
In-order Traversal: Traverse the BST in in-order to display the elements in sorted order.

Create a Main Function: Allow the user to interactively perform BST operations.

C Program to Implement Binary Search Tree

#include <stdio.h> #include <stdlib.h> // Define the structure for a tree node struct Node { int key; struct Node *left, *right; }; // Function to create a new node struct Node* newNode(int key) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->key = key; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with the given key struct Node* insert(struct Node* node, int key) { // If the tree is empty, return a new node if (node == NULL) { return newNode(key); } // Otherwise, recur down the tree if (key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the (unchanged) node pointer return node; } // Function to perform in-order traversal of the tree void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); } } // Function to search for a key in the BST struct Node* search(struct Node* root, int key) { // Base case: root is null or key is present at root if (root == NULL || root->key == key) { return root; } // Key is greater than root's key if (root->key < key) { return search(root->right, key); } // Key is smaller than root's key return search(root->left, key); } // Function to find the node with minimum key value (used in deletion) 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 the given key from the BST struct Node* deleteNode(struct Node* root, int key) { // Base case: if the tree is empty if (root == NULL) { return root; } // Otherwise, recur down the tree if (key < root->key) { root->left = deleteNode(root->left, key); } else if (key > root->key) { root->right = deleteNode(root->right, key); } 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->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } return root; } int main() { struct Node* root = NULL; int choice, key; while (1) { printf("\nBinary Search Tree Operations Menu:\n"); printf("1. Insert\n"); printf("2. Search\n"); printf("3. Delete\n"); printf("4. In-order Traversal\n"); printf("5. Exit\n"); printf("Enter your choice: "); scanf("%d", &choice); switch (choice) { case 1: printf("Enter the key to insert: "); scanf("%d", &key); root = insert(root, key); break; case 2: printf("Enter the key to search: "); scanf("%d", &key); struct Node* result = search(root, key); if (result != NULL) { printf("Key %d found in the BST.\n", key); } else { printf("Key %d not found in the BST.\n", key); } break; case 3: printf("Enter the key to delete: "); scanf("%d", &key); root = deleteNode(root, key); break; case 4: printf("In-order Traversal of the BST: "); inorder(root); printf("\n"); break; case 5: exit(0); default: printf("Invalid choice! Please enter a valid option.\n"); } } return 0; // Return 0 to indicate successful execution }

Explanation

Structure for a Tree Node

The struct Node defines a node of the binary search tree, which contains an integer key and pointers to its left and right children.

Function to Insert a Node

The insert function inserts a new node into the BST according to the binary search tree properties. If the tree is empty, it creates a new node; otherwise, it inserts the node in the correct position.

Function to Perform In-order Traversal

The inorder function recursively traverses the BST in in-order (left, root, right), which results in the nodes being visited in ascending order.

Function to Search for a Key

The search function searches for a given key in the BST. It recursively compares the key with the current node’s key and moves to the left or right subtree accordingly.

Function to Delete a Node

The deleteNode function removes a node with a specified key from the BST. It handles three cases:
1. Node with no child (leaf node).
2. Node with one child.
3. Node with two children (in which case the node is replaced with its in-order successor).

Main Function

The main function provides a menu-driven interface for performing operations on the BST, such as insertion, searching, deletion, and in-order traversal.

Output Example

Example Output:

Binary Search Tree Operations Menu: 1. Insert 2. Search 3. Delete 4. In-order Traversal 5. Exit Enter your choice: 1 Enter the key to insert: 20 Binary Search Tree Operations Menu: 1. Insert 2. Search 3. Delete 4. In-order Traversal 5. Exit Enter your choice: 1 Enter the key to insert: 10 Binary Search Tree Operations Menu: 1. Insert 2. Search 3. Delete 4. In-order Traversal 5. Exit Enter your choice: 1 Enter the key to insert: 30 Binary Search Tree Operations Menu: 1. Insert 2. Search 3. Delete 4. In-order Traversal 5. Exit Enter your choice: 4 In-order Traversal of the BST: 10 20 30

Example Output (Search and Delete):

Binary Search Tree Operations Menu: 1. Insert 2. Search 3. Delete 4. In-order Traversal 5. Exit Enter your choice: 2 Enter the key to search: 20 Key 20 found in the BST. Binary Search Tree Operations Menu: 1. Insert 2. Search 3. Delete 4. In-order Traversal 5. Exit Enter your choice: 3 Enter the key to delete: 20 Binary Search Tree Operations Menu: 1. Insert 2. Search 3. Delete 4. In-order Traversal 5. Exit Enter your choice: 4 In-order Traversal of the BST: 10 30

Conclusion

This C program demonstrates the implementation of a Binary Search Tree (BST) with basic operations like insertion, searching, deletion, and in-order traversal. BSTs are fundamental data structures that offer efficient search and modification operations. This program serves as a practical example for understanding BST operations in C programming.