Index
Binary Search Trees
A Binary Search Tree (BST) is a binary tree data structure with the following properties:
- Value Ordering: Each node in the BST has a value, and the values in the left subtree of a node are less than the value of the node, while the values in the right subtree are greater than the value of the node.
- Binary Tree Structure: Each node in the BST has at most two children, referred to as the left child and the right child.
The ordering property of BSTs makes searching, insertion, and deletion operations efficient, typically with average time complexity of O(log n), where n is the number of nodes in the tree. However, in the worst case, the time complexity can be O(n) if the tree becomes unbalanced.
Here’s a simple implementation of a Binary Search Tree in C:
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a new node into the binary search tree
struct TreeNode* insert(struct TreeNode* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
// Function to perform an in-order traversal of the binary tree (for testing)
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// Main function
int main() {
struct TreeNode* root = NULL;
// Insert elements into the binary search tree
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// Print the elements of the binary search tree (in-order traversal)
printf("In-order traversal of the binary search tree: ");
inOrderTraversal(root);
printf("\n");
return 0;
}
Output:
In-order traversal of the binary search tree: 20 30 40 50 60 70 80
Search for a value in BST
To search for a value in a Binary Search Tree (BST), you can traverse the tree starting from the root node and compare the value you are searching for with the values in each node. Here’s how you can implement the search algorithm in C:
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to search for a value in the binary search tree
struct TreeNode* search(struct TreeNode* root, int value) {
// If the tree is empty or the value is found at the root
if (root == NULL || root->data == value) {
return root;
}
// If the value is less than the root's data, search the left subtree
if (value < root->data) {
return search(root->left, value);
}
// If the value is greater than the root's data, search the right subtree
return search(root->right, value);
}
// Main function
int main() {
struct TreeNode* root = NULL;
// Insert elements into the binary search tree
root = createNode(50);
root->left = createNode(30);
root->right = createNode(70);
root->left->left = createNode(20);
root->left->right = createNode(40);
root->right->left = createNode(60);
root->right->right = createNode(80);
// Search for values in the binary search tree
int valueToSearch = 20;
struct TreeNode* result = search(root, valueToSearch);
if (result != NULL) {
printf("Value %d found in the binary search tree.\n", valueToSearch);
} else {
printf("Value %d not found in the binary search tree.\n", valueToSearch);
}
// Free dynamically allocated memory
free(root->left->left);
free(root->left->right);
free(root->left);
free(root->right->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
Output:
Value 20 found in the binary search tree.
Insert Node in BST
To insert a node into a Binary Search Tree (BST), you need to maintain the ordering property of the BST. Here’s how you can implement the insertion algorithm in C:
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a new node into the binary search tree
struct TreeNode* insert(struct TreeNode* root, int value) {
// If the tree is empty, create a new node and return it
if (root == NULL) {
return createNode(value);
}
// Otherwise, recur down the tree
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
// Return the unchanged node pointer
return root;
}
// Function to perform an in-order traversal of the binary tree (for testing)
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// Main function
int main() {
struct TreeNode* root = NULL;
// Insert elements into the binary search tree
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// Print the elements of the binary search tree (in-order traversal)
printf("In-order traversal of the binary search tree: ");
inOrderTraversal(root);
printf("\n");
// Free dynamically allocated memory
// Note: It's essential to implement proper memory deallocation logic in real-world scenarios
free(root->left->left);
free(root->left->right);
free(root->left);
free(root->right->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
Output:
In-order traversal of the binary search tree: 20 30 40 50 60 70 80
Delete a Node in a BST
Deleting a node from a Binary Search Tree (BST) involves maintaining the ordering property of the tree while removing the node. There are three cases to consider when deleting a node from a BST:
- Node to be deleted has no children (leaf node): In this case, simply remove the node from the tree.
- Node to be deleted has one child: In this case, replace the node to be deleted with its child.
- Node to be deleted has two children: In this case, find the inorder successor (or predecessor) of the node to be deleted, which is the smallest (or largest) node in its right (or left) subtree. Replace the node to be deleted with the inorder successor (or predecessor), and delete the inorder successor (or predecessor) from its original position.
Here’s the C code implementing the deletion operation in a BST:
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to find the minimum value node in a binary tree
struct TreeNode* findMinNode(struct TreeNode* node) {
struct TreeNode* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
// Function to delete a node from the binary search tree
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
if (root == NULL) {
return root;
}
// If the key to be deleted is smaller than the root's key, go to 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, go to the right subtree
else if (key > root->data) {
root->right = deleteNode(root->right, key);
}
// If the key is the same as the 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 TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct TreeNode* temp = root->left;
free(root);
return temp;
}
// Node with two children: Get the inorder successor (smallest in the right subtree)
struct TreeNode* temp = findMinNode(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;
}
// Function to perform an in-order traversal of the binary tree (for testing)
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// Main function
int main() {
struct TreeNode* root = createNode(50);
root->left = createNode(30);
root->right = createNode(70);
root->left->left = createNode(20);
root->left->right = createNode(40);
root->right->left = createNode(60);
root->right->right = createNode(80);
printf("Binary search tree before deletion:\n");
inOrderTraversal(root);
printf("\n");
// Delete node with value 30
root = deleteNode(root, 30);
printf("Binary search tree after deletion:\n");
inOrderTraversal(root);
printf("\n");
// Clean up memory
// (You may need to implement a separate function to deallocate memory properly)
return 0;
}
Output:
Binary search tree before deletion:
20 30 40 50 60 70 80
Binary search tree after deletion:
20 40 50 60 70 80
Time Complexity:
In a balanced BST:
- Search Operation: Since the tree is balanced, the search operation has a time complexity of O(log n), where n is the number of nodes in the tree. This is because the height of a balanced BST is approximately logarithmic to the number of nodes.
- Insertion and Deletion Operations: With balanced trees, insertion and deletion operations also have a time complexity of O(log n). Balancing operations may take additional time, but they are infrequent and amortized over multiple operations.
