A Binary Search Tree (BST) is a special type of binary tree where nodes are arranged in a specific order to allow efficient searching, insertion, and deletion operations. The BST property states:
- For any node N:
- All nodes in the left subtree of N have values less than or equal to the value of N.
- All nodes in the right subtree of N have values greater than the value of N.
- No duplicate nodes are allowed in a typical BST.
Key Operations in a BST
- Search: O(h)O(h)O(h) (h = height of the tree).
- Insertion: O(h)O(h)O(h).
- Deletion: O(h)O(h)O(h).
Implementation of a BST in C
1. Node Structure
The structure of a BST node:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
- data: Stores the value of the node.
- left: Points to the left child.
- right: Points to the right child.
2. Creating a New Node
A function to create a new node dynamically:
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf(“Memory allocation failed.\n”);
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
3. Inserting a Node
Insertion in a BST follows the BST property:
Node* insert(Node* root, int data) {
if (root == NULL) {
return createNode(data); // Insert at the root if the tree is empty
}
if (data < root->data) {
root->left = insert(root->left, data); // Insert in the left subtree
} else if (data > root->data) {
root->right = insert(root->right, data); // Insert in the right subtree
}
return root; // Return unchanged node pointer
}
4. Searching for a Node
Searching for a node involves comparing the key with the root and traversing left or right:
Node* search(Node* root, int key) {
if (root == NULL || root->data == key) {
return root; // Return the node if found, or NULL if not found
}
if (key < root->data) {
return search(root->left, key); // Search in the left subtree
}
return search(root->right, key); // Search in the right subtree
}
5. Traversing the BST
Traversal methods include in-order, pre-order, and post-order.
- In-order Traversal (Left → Root → Right): Produces a sorted sequence of values in BST.
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf(“%d “, root->data);
inorderTraversal(root->right);
}
}
6. Deleting a Node
Deleting a node in a BST involves three cases:
- Node with no children (leaf node): Simply remove the node.
- Node with one child: Replace the node with its child.
- Node with two children: Replace the node with its in-order successor (smallest node in the right subtree).
Node* findMin(Node* root) {
while (root->left != NULL) {
root = root->left; // Find the leftmost node
}
return root;
}
Node* deleteNode(Node* root, int key) {
if (root == NULL) {
return root; // Return if tree is empty or node not found
}
if (key < root->data) {
root->left = deleteNode(root->left, key); // Traverse left
} else if (key > root->data) {
root->right = deleteNode(root->right, key); // Traverse right
} else {
// Node to be deleted found
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 = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
7. Main Function
A demonstration of the above functions:
int main() {
Node* root = NULL;
// Insert nodes
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);
printf(“In-order Traversal of BST: “);
inorderTraversal(root);
printf(“\n”);
// Search for a node
int key = 40;
Node* result = search(root, key);
if (result != NULL) {
printf(“Node %d found in the BST.\n”, key);
} else {
printf(“Node %d not found in the BST.\n”, key);
}
// Delete a node
root = deleteNode(root, 50);
printf(“In-order Traversal after deletion: “);
inorderTraversal(root);
printf(“\n”);
return 0;
}
Output Example
For the above program:
mathematica
Copy code
In-order Traversal of BST: 20 30 40 50 60 70 80
Node 40 found in the BST.
In-order Traversal after deletion: 20 30 40 60 70 80
Advantages of BST
- Efficient searching, insertion, and deletion (average-case O(logn)O(\log n)O(logn)).
- Maintains elements in sorted order.
Limitations
- If the BST is unbalanced (e.g., skewed tree), the performance degrades to O(n)O(n)O(n).
- Additional balancing (e.g., AVL Tree, Red-Black Tree) is required for consistent performance.