Real-Life Applications
Binary search trees
BST are used in various real life applications:
Database Indexing:
Using a binary tree eliminates the need to sort the master list before searching. When you have a sorted list ,you can effectively use binary search to search through the list. Database indexes are data structures of indexed data. Binary search calculates the next position midpoint at each step.
File Systems:
File systems use BSTs to maintain directory structures for quick lookup of files and directories. For example the Windows NTFS file system uses BSTs to store the Master File Table (MFT) which contains information about all the files on the hard drive.
Computer Networks: Binary search tree can be used in computer network to store routing tables .
Spell Checkers:
A binary tree must be created before spell checking. Each node has a letter starting with each letter as root. The left child and the right child have another letter resulting in a potentially valid word. A dictionary application uses BSTs to effectively store and search words.
#include<stdio.h>
#include<stdlib.h>
// Structure for a BST node
struct Node {
int data;
struct Node *left;
struct Node *right;
};
// Function to create a new BST node
struct Node *createNode(int data) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
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 node into the BST
struct Node *insert(struct Node *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 search for a node in the BST
struct Node *search(struct Node *root, int key) {
if (root == NULL || root->data == key) {
return root;
}
if (key < root->data) {
return search(root->left, key);
}
return search(root->right, key);
}
// Function to perform inorder traversal of the BST (left-root-right)
void inorder(struct Node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Function to perform preorder traversal of the BST (root-left-right)
void preorder(struct Node *root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
// Function to perform postorder traversal of the BST (left-right-root)
void postorder(struct Node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
// Function to free memory allocated for the BST nodes
void freeBST(struct Node *root) {
if (root != NULL) {
freeBST(root->left);
freeBST(root->right);
free(root);
}
}
// Main function to demonstrate BST operations
int main() {
struct Node *root = NULL;
int choice, data, key;
printf("Binary Search Tree Operations\n");
while (1) {
printf("\n1. Insert\n");
printf("2. Search\n");
printf("3. Display Inorder\n");
printf("4. Display Preorder\n");
printf("5. Display Postorder\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data to insert: ");
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
printf("Enter data to search: ");
scanf("%d", &key);
struct Node *result = search(root, key);
if (result != NULL) {
printf("%d found in the tree.\n", key);
} else {
printf("%d not found in the tree.\n", key);
}
break;
case 3:
printf("Inorder traversal: ");
inorder(root);
printf("\n");
break;
case 4:
printf("Preorder traversal: ");
preorder(root);
printf("\n");
break;
case 5:
printf("Postorder traversal: ");
postorder(root);
printf("\n");
break;
case 6:
printf("Exiting program.\n");
freeBST(root); // Free allocated memory before exiting
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}
Output
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 1
Enter data to insert: 10
10 inserted into the tree.
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 1
Enter data to insert: 5
5 inserted into the tree.
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 1
Enter data to insert: 20
20 inserted into the tree.
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 2
Enter data to search: 5
5 found in the tree.
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 2
Enter data to search: 15
15 not found in the tree.
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 3
Inorder traversal: 5 10 20
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 4
Preorder traversal: 10 5 20
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 5
Postorder traversal: 5 20 10
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice: 6
Exiting program.
Program Explanation
The C program shows how different operations can be done on a Binary Search Tree (BST). It involves the functions to insert, search and display nodes in BST using three methods of traversal that are inorder, preorder, and postorder. Let us analyze in detail the output produced by this program.
1. Initialization of the Program and User Prompt
Upon beginning its execution, it sets root as NULL so as to initialize tree as an empty BST. From here, user is presented with a menu to select an operation:
Binary Search Tree Operations
1. Insert
2. Search
3. Display Inorder
4. Display Preorder
5. Display Postorder
6. Exit
Enter your choice:
2. Insert Operation
To add a node (option 1), the program will ask for the data to be inserted:
Enter the data to insert.
1.Creating a New Node: createNode is called memory for a new node is allocated. Also this function initializes left and right pointers of the node to NULL and sets its data value as specified.
2. Inserting into the BST: depending on its value, when it comes to finding out where exactly would the new node go, this has been accomplished by means of an insert function. In case root is NULL implying that tree is empty then this will become root otherwise it moves through tree and compares new value with old values in order to find a proper place.
3. Search Operation
When the user chooses the option to search, the program prompts them to enter the information they are looking for.
Enter data to search:
The program searches within the binary search tree (BST): The search function navigates through the tree to locate the node that contains the specific key. It starts at the root, which is the top of the tree, and decides to move left or right depending on whether the key is less than or greater than the data in the current node. If the key is located, the function returns the node. If the key is not found, the function returns nothing (NULL).
The program then informs the user whether the search was successful:
5 found in the tree.
4. Inorder Traversal
If the user selects inorder traversal (option 3) the program carries out and shows the traversal in inorder sequence.
Inorder Traversal: The inorder function follows the sequence of left-root-right. It first visits nodes in the left subtree, then the root node, and finally nodes in the right subtree. This method of traversal displays the node values in ascending order.
5. Preorder Traversal
If the user selects preorder traversal (option 4), the program carries out and shows the traversal in preorder sequence:
