Binary Search Tree in C: Menu-Driven Program for Insert, Delete, Copy and Equality
Introduction
A Binary Search Tree (BST) is one of the most commonly used tree data structures in computer science. It stores elements in an organized manner that makes searching, insertion, and deletion easier compared with an unsorted collection.In this tutorial, we will understand the concept of a Binary Search Tree and implement a menu-driven C program to perform common BST operations such as:
Insert a node
Delete a node
Inorder traversal
Preorder traversal
Postorder traversal
Copy a binary search tree
Check whether two trees are equal
Display the tree structure
The program also demonstrates how a menu-driven application can be implemented using a switch statement in C.
Table of Contents
What is a Binary Search Tree?
Properties of a BST
Example of a Binary Search Tree
What is a Menu-Driven Program?
BST Operations
C Program for Binary Search Tree
Explanation of the Program
How BST Deletion Works
Copying a Binary Search Tree
Comparing Two Binary Search Trees
Tree Traversals
Time Complexity
Sample Operations
Conclusion
What is a Binary Search Tree?
A Binary Search Tree, commonly called a BST, is a binary tree in which every node can have at most two children.
The two child nodes are generally referred to as:
Left child
Right child
A BST follows an important ordering rule:
Values smaller than a node are stored in its left subtree, while values greater than the node are stored in its right subtree.
For example, if we insert the values:
50, 30, 70, 20, 40, 60, 80
the resulting BST looks like this:
50
/ \
30 70
/ \ / \
20 40 60 80
Here:
20,30, and40belong to the left side of50.60,70, and80belong to the right side of50.The same ordering rule applies recursively to every subtree.
Properties of a Binary Search Tree
A Binary Search Tree generally follows these rules:
Each node has at most two children.
Values smaller than the current node are placed in the left subtree.
Values greater than the current node are placed in the right subtree.
Searching can be performed by repeatedly choosing either the left or right subtree.
Inorder traversal of a valid BST produces values in sorted order.
Duplicate values are usually either rejected or handled using a predefined duplicate policy.
In the program below, duplicate values are not inserted.
What is a Menu-Driven Program?
A menu-driven program displays a list of operations and allows the user to select an operation.
For example:
1. Insert
2. Delete
3. Inorder Traversal
4. Preorder Traversal
5. Postorder Traversal
6. Copy Tree
7. Compare Trees
8. Display Tree
9. Exit
The user enters an option, and the program performs the corresponding operation.
In C, a switch statement is commonly used to implement this type of program.
Binary Search Tree Operations
The program in this tutorial supports the following operations.
1. Insert a node
Adds a new value to the BST while maintaining the BST ordering property.
2. Delete a node
Removes a value from the tree while preserving the BST structure.
3. Preorder traversal
Visits nodes in this order:
Root → Left → Right
4. Postorder traversal
Visits nodes in this order:
Left → Right → Root
5. Inorder traversal
Visits nodes in this order:
Left → Root → Right
For a BST, inorder traversal produces the values in ascending order.
6. Copy a tree
Creates another tree containing the same values and structure.
7. Compare two trees
Checks whether two trees contain the same values in the same structural arrangement.
8. Display the tree
Prints the tree in a sideways format so that its structure is easier to understand.
C Program: Menu-Driven Binary Search Tree
The following program implements a menu-driven BST using C.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left;
struct node *right;
};
/* Function prototypes */
struct node *newNode(int data);
struct node *insert(struct node *root, int data);
struct node *deleteNode(struct node *root, int data);
struct node *findMin(struct node *root);
void inorder(struct node *root);
void preorder(struct node *root);
void postorder(struct node *root);
void display(struct node *root, int level);
struct node *copyTree(struct node *root);
int areEqual(struct node *tree1, struct node *tree2);
int main(void)
{
struct node *root = NULL;
struct node *copiedTree = NULL;
int choice;
int data;
while (1)
{
printf("\n========================================\n");
printf(" BINARY SEARCH TREE MENU\n");
printf("========================================\n");
printf("1. Insert a node\n");
printf("2. Delete a node\n");
printf("3. Preorder Traversal\n");
printf("4. Postorder Traversal\n");
printf("5. Inorder Traversal\n");
printf("6. Copy the tree\n");
printf("7. Compare two trees\n");
printf("8. Display tree\n");
printf("9. Exit\n");
printf("========================================\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter the value to insert: ");
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
printf("Enter the value to delete: ");
scanf("%d", &data);
root = deleteNode(root, data);
break;
case 3:
printf("Preorder Traversal: ");
preorder(root);
printf("\n");
break;
case 4:
printf("Postorder Traversal: ");
postorder(root);
printf("\n");
break;
case 5:
printf("Inorder Traversal: ");
inorder(root);
printf("\n");
break;
case 6:
copiedTree = copyTree(root);
printf("Tree copied successfully.\n");
printf("Copied tree (Inorder): ");
inorder(copiedTree);
printf("\n");
break;
case 7:
if (areEqual(root, copiedTree))
printf("Both trees are equal.\n");
else
printf("The trees are not equal.\n");
break;
case 8:
printf("\nTree structure:\n");
display(root, 0);
break;
case 9:
printf("Program terminated.\n");
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}
/* Create a new node */
struct node *newNode(int data)
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
if (temp == NULL)
{
printf("Memory allocation failed.\n");
exit(1);
}
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Insert a value into the BST */
struct node *insert(struct node *root, int data)
{
if (root == NULL)
return newNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
else
printf("%d already exists in the tree.\n", data);
return root;
}
/* Find the smallest node in a subtree */
struct node *findMin(struct node *root)
{
if (root == NULL)
return NULL;
while (root->left != NULL)
root = root->left;
return root;
}
/* Delete a node from the BST */
struct node *deleteNode(struct node *root, int data)
{
if (root == NULL)
{
printf("%d was not found in the tree.\n", data);
return NULL;
}
if (data < root->data)
{
root->left = deleteNode(root->left, data);
}
else if (data > root->data)
{
root->right = deleteNode(root->right, data);
}
else
{
/* Case 1 and Case 2:
Node has zero or one child */
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
/* Case 3:
Node has two children */
struct node *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
/* Inorder traversal */
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
/* Preorder traversal */
void preorder(struct node *root)
{
if (root != NULL)
{
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
/* Postorder traversal */
void postorder(struct node *root)
{
if (root != NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
/* Display the tree sideways */
void display(struct node *root, int level)
{
int i;
if (root == NULL)
return;
display(root->right, level + 1);
printf("\n");
for (i = 0; i < level; i++)
printf("\t");
printf("%d", root->data);
display(root->left, level + 1);
}
/* Copy a binary tree */
struct node *copyTree(struct node *root)
{
struct node *copy;
if (root == NULL)
return NULL;
copy = newNode(root->data);
copy->left = copyTree(root->left);
copy->right = copyTree(root->right);
return copy;
}
/* Compare two trees */
int areEqual(struct node *tree1, struct node *tree2)
{
if (tree1 == NULL && tree2 == NULL)
return 1;
if (tree1 == NULL || tree2 == NULL)
return 0;
return (
tree1->data == tree2->data &&
areEqual(tree1->left, tree2->left) &&
areEqual(tree1->right, tree2->right)
);
}
Understanding the Node Structure
Each BST node contains three fields:
struct node {
int data;
struct node *left;
struct node *right;
};
The data field stores the value.
The left pointer points to the left child, while the right pointer points to the right child.
For example:
[50]
/ \
/ \
[30] [70]
The node containing 50 stores pointers to the nodes containing 30 and 70.
Inserting a Node into the BST
The insertion operation starts at the root.
Suppose the tree contains:
50
/ \
30 70
If we want to insert 40:
Compare
40with50.40 < 50, so move to the left subtree.Compare
40with30.40 > 30, so move to the right.The right position of
30is empty.Insert
40.
The resulting tree becomes:
50
/ \
30 70
\
40
The insertion function maintains the BST ordering property.
Deleting a Node from a BST
Deletion is slightly more complicated because a node can have zero, one, or two children.
Case 1: Leaf Node
A leaf node has no children.
Example:
50
/ \
30 70
Deleting 30 simply removes the node.
50
\
70
Case 2: Node with One Child
Consider:
50
/
30
\
40
If 30 is deleted, its child 40 takes its position.
The tree becomes:
50
/
40
Case 3: Node with Two Children
This is the most important deletion case.
Consider:
50
/ \
30 70
/ \
60 80
Suppose we delete 70.
The node has two children, so we find its inorder successor.
The inorder successor is the smallest value in the right subtree.
For 70, the right subtree contains:
80
Therefore, 80 can replace 70.
The resulting tree is:
50
/ \
30 80
/
60
The program finds the smallest node using:
struct node *findMin(struct node *root)
{
if (root == NULL)
return NULL;
while (root->left != NULL)
root = root->left;
return root;
}
Copying a Binary Search Tree
Copying a tree means creating a new tree containing the same node values and the same structure.
For example:
Original:
50
/ \
30 70
The copied tree should be:
Copy:
50
/ \
30 70
The nodes are separately allocated in memory, so modifying one tree does not directly modify the other.
The copy function recursively creates corresponding left and right subtrees:
struct node *copyTree(struct node *root)
{
if (root == NULL)
return NULL;
struct node *copy = newNode(root->data);
copy->left = copyTree(root->left);
copy->right = copyTree(root->right);
return copy;
}
Checking Equality of Two Trees
Two binary trees are considered equal when:
Both trees are empty, or
Their corresponding nodes contain the same values, and
Their left subtrees are equal, and
Their right subtrees are equal.
For example:
Tree 1: Tree 2:
50 50
/ \ / \
30 70 30 70
These trees are equal because their values and structures match.
However:
Tree 1: Tree 2:
50 50
/ \ / \
30 70 40 70
These trees are not equal because the corresponding left nodes contain different values.
The comparison is implemented using:
int areEqual(struct node *tree1, struct node *tree2)
{
if (tree1 == NULL && tree2 == NULL)
return 1;
if (tree1 == NULL || tree2 == NULL)
return 0;
return (
tree1->data == tree2->data &&
areEqual(tree1->left, tree2->left) &&
areEqual(tree1->right, tree2->right)
);
}
Binary Tree Traversals
Tree traversal means visiting every node in a particular order.
The program implements three common depth-first traversals.
Inorder Traversal
Order:
Left → Root → Right
For:
50
/ \
30 70
/ \ / \
20 40 60 80
the inorder traversal is:
20 30 40 50 60 70 80
One important property of a BST is that inorder traversal produces sorted values.
Preorder Traversal
Order:
Root → Left → Right
Output:
50 30 20 40 70 60 80
Preorder traversal is useful for representing or reconstructing tree structures.
Postorder Traversal
Order:
Left → Right → Root
Output:
20 40 30 60 80 70 50
Postorder traversal is commonly useful when nodes need to be processed or freed from the bottom of the tree upward.
Time Complexity of BST Operations
Let h represent the height of the tree.
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Traversal | O(n) | O(n) |
| Copy Tree | O(n) | O(n) |
| Compare Trees | O(n) | O(n) |
A balanced BST has a height close to log₂(n), allowing efficient searching, insertion, and deletion.
However, if values are inserted in an already sorted order, an ordinary BST can become highly unbalanced:
10
\
20
\
30
\
40
\
50
In this situation, the tree behaves similarly to a linked list, making operations potentially O(n).
Self-balancing trees such as AVL trees and Red-Black trees are designed to reduce this problem.
Example Menu Execution
Suppose the user inserts:
50
30
70
20
40
60
80
The tree becomes:
50
/ \
30 70
/ \ / \
20 40 60 80
Selecting Inorder Traversal produces:
20 30 40 50 60 70 80
Selecting Preorder Traversal produces:
50 30 20 40 70 60 80
Selecting Postorder Traversal produces:
20 40 30 60 80 70 50
If we delete 70, the program finds its inorder successor and reorganizes the affected portion of the tree.
Important Note About Recursion
Although the original problem statement may describe the required operations as non-recursive, the commonly used implementation of BST insertion, deletion, traversal, copying, and equality can be recursive.
The program presented above uses recursion for several tree operations because recursion naturally follows the hierarchical structure of a binary tree.
If your college assignment specifically requires strictly non-recursive implementations, the functions should instead use techniques such as:
Explicit stacks
Iterative pointer traversal
Queues where appropriate
Therefore, check the exact wording of your laboratory or examination question before submitting the program.
Common Viva Questions
What is a Binary Search Tree?
A BST is a binary tree in which values smaller than a node are placed in its left subtree and values greater than the node are placed in its right subtree.
What is the root of a tree?
The topmost node of a tree is called the root.
What is a leaf node?
A node with no left or right child is called a leaf node.
What is the advantage of a BST?
A reasonably balanced BST can provide efficient search, insertion, and deletion operations.
What happens if a BST becomes skewed?
Its height can become O(n), causing search, insertion, and deletion to degrade to O(n).
Which traversal gives sorted output for a BST?
Inorder traversal.
What are the three deletion cases?
A node may have:
No child
One child
Two children
When a node has two children, its inorder successor or inorder predecessor can be used to replace it.
Conclusion
A Binary Search Tree is an important data structure for understanding hierarchical data and efficient searching. Its ordering property makes operations such as insertion, searching, and deletion straightforward when the tree remains reasonably balanced.
In this C tutorial, we created a menu-driven Binary Search Tree program supporting insertion, deletion, tree traversal, tree copying, equality checking, and visual tree display.
Understanding BSTs also provides a strong foundation for learning more advanced data structures such as AVL Trees, Red-Black Trees, Heaps, and other balanced search trees.
If you are preparing for a C programming laboratory, data structures examination, viva, or coding interview, understanding the three deletion cases and why inorder traversal produces sorted output is especially important.
0 Comments
If you have any doubts or any topics that you want to know more about them please let me know