Binary Search Tree (BST)
A Binary Search Tree (BST) is a binary tree with the following properties:
1. Structure:
*Each node has at most two children: left and right.
*The left child contains a value smaller than the parent node.
*The right child contains a value larger than the parent node.
*Search: To find if a value exists in the tree.
*Insertion: To add a new value while maintaining the BST properties.
*Deletion: To remove a value while maintaining the BST properties.
*Traversal: To visit all nodes in specific orders (e.g., in-order, pre-order, post-order).
Efficiency of Binary Search Tree
Time Complexity (in terms of height h):
Best Case: When the tree is perfectly balanced:
*Search, Insertion, Deletion: O(log n)
Worst Case: When the tree is skewed (like a linked list):
* Search, Insertion, Deletion: O(n).
* Space Complexity: O(n) for the storage of nodes.
Real-World Applications of BST
1. Database Indexing
BSTs are used to organize and search database records efficiently.
A balanced BST ensures quick lookup times.
2. Auto-complete Systems
Used in search engines or text editors to quickly retrieve and suggest words based on prefixes.
3. File System
File indexing systems often rely on BSTs to manage file metadata.
4. Routing Tables in Networks
BSTs are used to implement routing tables for quick data retrieval.
5. Gaming
Used for decision-making trees in games where the data needs to be searched quickly.
6. Dictionary Implementation
BSTs are used to implement dictionaries for fast key-value pair lookups.
---
CODE IMPLEMENTATION IN LAB
#include <cstdlib>
using namespace std;
struct tree {
int data;
struct tree* left;
struct tree* right;
};
typedef struct tree TREE;
class BST {
public:
TREE* insert_into_bst(TREE*, int);
void inorder(TREE*);
void preorder(TREE*);
void postorder(TREE*);
TREE* delete_from_bst(TREE*, int);
int count_nodes(TREE*);
int count_edges(TREE*);
int count_greater_than(TREE*, int);
int count_lesser_than(TREE*, int);
TREE* find_min(TREE*);
TREE* find_max(TREE*);
TREE* delete_less_than(TREE*, int);
TREE* delete_greater_than(TREE*, int);
TREE* tree_search(TREE*, int);
TREE* inorder_successor(TREE*, int);
TREE* inorder_predecessor(TREE*, int);
int count_leaf_nodes(TREE*);
int count_external_nodes(TREE*);
int calculate_memory_usage(TREE*);
int count_edges_to_max(TREE*);
void print_root_address(TREE*);
int search_with_comparisons(TREE*, int, int&);
int count_level_1_nodes(TREE*);
TREE* make_duplicate(TREE*);
};
// Function to insert a node into the BST
TREE* BST::insert_into_bst(TREE* root, int data) {
TREE* newnode = (TREE*)malloc(sizeof(TREE));
if (newnode == NULL) {
cout << "Memory allocation failed" << endl;
return root;
}
newnode->data = data;
newnode->left = NULL;
newnode->right = NULL;
if (root == NULL) {
root = newnode;
cout << "Root node inserted into tree" << endl;
return root;
}
TREE* currnode = root;
TREE* parent = NULL;
while (currnode != NULL) {
parent = currnode;
if (newnode->data < currnode->data)
currnode = currnode->left;
else
currnode = currnode->right;
}
if (newnode->data < parent->data)
parent->left = newnode;
else
parent->right = newnode;
cout << "Node inserted successfully" << endl;
return root;
}
// Function to perform inorder traversal
void BST::inorder(TREE* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << "\t";
inorder(root->right);
}
}
// Function to perform preorder traversal
void BST::preorder(TREE* root) {
if (root != NULL) {
cout << root->data << "\t";
preorder(root->left);
preorder(root->right);
}
}
// Function to perform postorder traversal
void BST::postorder(TREE* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->data << "\t";
}
}
// Function to delete a node from the BST
TREE* BST::delete_from_bst(TREE* root, int data) {
TREE* currnode = root;
TREE* parent = NULL;
TREE* successor = NULL;
TREE* p = NULL;
if (root == NULL) {
cout << "Tree is empty" << endl;
return root;
}
while (currnode != NULL && currnode->data != data) {
parent = currnode;
if (data < currnode->data)
currnode = currnode->left;
else
currnode = currnode->right;
}
if (currnode == NULL) {
cout << "Item not found" << endl;
return root;
}
if (currnode->left == NULL)
p = currnode->right;
else if (currnode->right == NULL)
p = currnode->left;
else {
successor = currnode->right;
TREE* successorParent = currnode;
while (successor->left != NULL) {
successorParent = successor;
successor = successor->left;
}
currnode->data = successor->data;
if (successorParent->left == successor)
successorParent->left = successor->right;
else
successorParent->right = successor->right;
free(successor);
return root;
}
if (parent == NULL) {
free(currnode);
return p;
}
if (currnode == parent->left)
parent->left = p;
else
parent->right = p;
free(currnode);
return root;
}
// Count the total number of nodes
int BST::count_nodes(TREE* root) {
if (root == NULL)
return 0;
return 1 + count_nodes(root->left) + count_nodes(root->right);
}
// Count edges (total nodes - 1)
int BST::count_edges(TREE* root) {
return count_nodes(root) - 1;
}
// Count nodes greater than K
int BST::count_greater_than(TREE* root, int K) {
if (root == NULL)
return 0;
int count = (root->data > K) ? 1 : 0;
return count + count_greater_than(root->left, K) + count_greater_than(root->right, K);
}
// Count nodes less than K
int BST::count_lesser_than(TREE* root, int K) {
if (root == NULL)
return 0;
int count = (root->data < K) ? 1 : 0;
return count + count_lesser_than(root->left, K) + count_lesser_than(root->right, K);
}
// Delete nodes less than K
TREE* BST::delete_less_than(TREE* root, int K) {
if (root == NULL) return NULL;
if (root->data < K) return delete_less_than(root->right, K);
root->left = delete_less_than(root->left, K);
return root;
}
// Delete nodes greater than K
TREE* BST::delete_greater_than(TREE* root, int K) {
if (root == NULL) return NULL;
if (root->data > K) return delete_greater_than(root->left, K);
root->right = delete_greater_than(root->right, K);
return root;
}
// Find minimum node
TREE* BST::find_min(TREE* root) {
if (root == NULL)
return NULL;
while (root->left != NULL)
root = root->left;
return root;
}
// Find maximum node
TREE* BST::find_max(TREE* root) {
if (root == NULL)
return NULL;
while (root->right != NULL)
root = root->right;
return root;
}
// Inorder successor
TREE* BST::inorder_successor(TREE* root, int k) {
TREE* current = tree_search(root, k);
if (current == NULL || current->right == NULL)
return NULL;
TREE* temp = current->right;
while (temp->left != NULL)
temp = temp->left;
return temp;
}
// Inorder predecessor
TREE* BST::inorder_predecessor(TREE* root, int k) {
TREE* current = tree_search(root, k);
if (current == NULL || current->left == NULL)
return NULL;
TREE* temp = current->left;
while (temp->right != NULL)
temp = temp->right;
return temp;
}
// Tree search (Recursive)
TREE* BST::tree_search(TREE* x, int k) {
if (x == NULL || k == x->data)
return x;
if (k < x->data)
return tree_search(x->left, k);
else
return tree_search(x->right, k);
}
// Count leaf nodes
int BST::count_leaf_nodes(TREE* root) {
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return count_leaf_nodes(root->left) + count_leaf_nodes(root->right);
}
// Count external nodes (leaf nodes)
int BST::count_external_nodes(TREE* root) {
return count_leaf_nodes(root);
}
// Calculate memory occupied by the tree (size of each node * number of nodes)
int BST::calculate_memory_usage(TREE* root) {
return count_nodes(root) * sizeof(TREE);
}
// Count edges to maximum node
int BST::count_edges_to_max(TREE* root) {
int edges = 0;
while (root->right != NULL) {
root = root->right;
edges++;
}
return edges;
}
// Print address of root node
void BST::print_root_address(TREE* root) {
cout << "Address of the root node: " << root << endl;
}
// Search with comparisons
int BST::search_with_comparisons(TREE* root, int k, int& comparisons) {
comparisons = 0;
while (root != NULL) {
comparisons++;
if (k == root->data)
return 1;
else if (k < root->data)
root = root->left;
else
root = root->right;
}
return 0;
}
// Count level 1 nodes (nodes directly under the root)
int BST::count_level_1_nodes(TREE* root) {
if (root == NULL)
return 0;
int count = 0;
if (root->left != NULL)
count++;
if (root->right != NULL)
count++;
return count;
}
// Make a duplicate tree
TREE* BST::make_duplicate(TREE* root) {
if (root == NULL)
return NULL;
TREE* newnode = (TREE*)malloc(sizeof(TREE));
newnode->data = root->data;
newnode->left = make_duplicate(root->left);
newnode->right = make_duplicate(root->right);
return newnode;
}
int main() {
BST bst;
TREE* root = NULL;
int choice = 0, data = 0, K = 0;
int comparisons;
while (1) {
cout << "\n ** MENU **\n";
cout << "1. Insert into BST\n";
cout << "2. Inorder traversal\n";
cout << "3. Preorder traversal\n";
cout << "4. Postorder traversal\n";
cout << "5. Delete from BST\n";
cout << "6. Count total nodes\n";
cout << "7. Count edges\n";
cout << "8. Count nodes greater than K\n";
cout << "9. Count nodes less than K\n";
cout << "10. Delete nodes less than K\n";
cout << "11. Delete nodes greater than K\n";
cout << "12. Find minimum\n";
cout << "13. Find maximum\n";
cout << "14. Find inorder successor\n";
cout << "15. Find inorder predecessor\n";
cout << "16. Count leaf nodes\n";
cout << "17. Count external nodes\n";
cout << "18. Calculate memory usage\n";
cout << "19. Count edges to maximum node\n";
cout << "20. Print root node address\n";
cout << "21. Search with comparisons\n";
cout << "22. Count level 1 nodes\n";
cout << "23. Duplicate tree\n";
cout << "24. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter the item to insert: ";
cin >> data;
root = bst.insert_into_bst(root, data);
break;
case 2:
if (root == NULL)
cout << "Tree is empty\n";
else {
cout << "Inorder traversal is...\n";
bst.inorder(root);
cout << endl;
}
break;
case 3:
if (root == NULL)
cout << "Tree is empty\n";
else {
cout << "Preorder traversal is...\n";
bst.preorder(root);
cout << endl;
}
break;
case 4:
if (root == NULL)
cout << "Tree is empty\n";
else {
cout << "Postorder traversal is...\n";
bst.postorder(root);
cout << endl;
}
break;
case 5:
cout << "Enter the item to be deleted: ";
cin >> data;
root = bst.delete_from_bst(root, data);
break;
case 6:
cout << "Total nodes in the tree: " << bst.count_nodes(root) << endl;
break;
case 7:
cout << "Total edges in the tree: " << bst.count_edges(root) << endl;
break;
case 8:
cout << "Enter value K: ";
cin >> K;
cout << "Nodes greater than " << K << ": " << bst.count_greater_than(root, K) << endl;
break;
case 9:
cout << "Enter value K: ";
cin >> K;
cout << "Nodes less than " << K << ": " << bst.count_lesser_than(root, K) << endl;
break;
case 10:
cout << "Enter value K: ";
cin >> K;
root = bst.delete_less_than(root, K);
cout << "Nodes less than " << K << " have been deleted.\n";
break;
case 11:
cout << "Enter value K: ";
cin >> K;
root = bst.delete_greater_than(root, K);
cout << "Nodes greater than " << K << " have been deleted.\n";
break;
case 12:
if (root == NULL)
cout << "Tree is empty\n";
else
cout << "Minimum value in the tree: " << bst.find_min(root)->data << endl;
break;
case 13:
if (root == NULL)
cout << "Tree is empty\n";
else
cout << "Maximum value in the tree: " << bst.find_max(root)->data << endl;
break;
case 14:
cout << "Enter the item to find its inorder successor: ";
cin >> data;
{
TREE* successor = bst.inorder_successor(root, data);
if (successor != NULL)
cout << "Inorder successor: " << successor->data << endl;
else
cout << "No successor found.\n";
}
break;
case 15:
cout << "Enter the item to find its inorder predecessor: ";
cin >> data;
{
TREE* predecessor = bst.inorder_predecessor(root, data);
if (predecessor != NULL)
cout << "Inorder predecessor: " << predecessor->data << endl;
else
cout << "No predecessor found.\n";
}
break;
case 16:
cout << "Leaf nodes count: " << bst.count_leaf_nodes(root) << endl;
break;
case 17:
cout << "External nodes count: " << bst.count_external_nodes(root) << endl;
break;
case 18:
cout << "Memory used by the tree: " << bst.calculate_memory_usage(root) << " bytes\n";
break;
case 19:
cout << "Edges to maximum node: " << bst.count_edges_to_max(root) << endl;
break;
case 20:
bst.print_root_address(root);
break;
case 21:
cout << "Enter the item to search: ";
cin >> data;
if (bst.search_with_comparisons(root, data, comparisons))
cout << "Item found with " << comparisons << " comparisons.\n";
else
cout << "Item not found after " << comparisons << " comparisons.\n";
break;
case 22:
cout << "Level 1 nodes count: " << bst.count_level_1_nodes(root) << endl;
break;
case 23:
{
TREE* duplicate_tree = bst.make_duplicate(root);
cout << "Duplicate tree created. Inorder traversal of duplicate tree:\n";
bst.inorder(duplicate_tree);
cout << endl;
}
break;
case 24:
cout << "Exiting...\n";
exit(0);
default:
cout << "Invalid choice.\n";
}
}
return 0;
}
OUTPUT
MENU
1. Insert into BST
2. Inorder traversal
3. Preorder traversal
4. Postorder traversal
5. Delete from BST
6. Count total nodes
7. Count edges
8. Count nodes greater than K
9. Count nodes less than K
10. Delete nodes less than K
11. Delete nodes greater than K
12. Find minimum
13. Find maximum
14. Find inorder successor
15. Find inorder predecessor
16. Count leaf nodes
17. Count external nodes
18. Calculate memory usage
19. Count edges to maximum node
20. Print root node address
21. Search with comparisons
22. Count level 1 nodes
23. Duplicate tree
24. Exit
Enter your choice: 1
Enter the item to insert: 10
Root node inserted into tree
ABOVE CODE CAN BE IMPLEMENTED BASED ON THE ABOVE MENU