The Islamia University of Bahawalpur
Faculty of Engineering
BS Cyber Security and Digital Forensics 3rd semester
Lab # 9 Binary Search Trees
Course: Data Structures and Algorithms lab Date:
Submitted by: Ambreena Munir Roll No. F23BINCE1M04005
Objectives
The purpose of this lab session is to understand the implementation of operations on binary
trees.
Binary Search Trees:
A binary tree is a tree in which no node can have more than two children. In a binary search
tree ,for every node, X, in the tree, the values of all the keys in its left sub tree are smaller than
the key value of X, and the values of all the keys in its right sub tree are larger than the key
value of X. The basic operations on a binary search tree take time proportional to the height of
the tree.
In the linked list implementation of binary search trees: Each element is represented by node
with two link fields and a data field. Each connecting line (or edge) in a binary tree drawing will
be represented by a link field. A leaf node has a leftChild and rightChild link of NULL. Root node
will be pointed to by a pointer variable.
Algorithm:
1. Create a structure with an element (Element) and two pointers – Left and Right that points to
the left and right child node respectively in the tree.
2. Create a new node and assign the resultant pointer variable to the root node pointer T and
assign it to NULL.
3. To insert a new element X into the tree:
a. If the value of T is NULL, assign T->Element to X, and the left and right child pointers to NULL
and exit the insertion operation.
b. Otherwise if the element to be inserted is less than the root element T, repeat the step 3
recursively, with the new value of T as T->Left.
c. Otherwise if the element to be inserted is more than the root element T, repeat the step 3
recursively, with the new value of T as T->Right.
d. If the element is already present in the tree, do nothing.
4. To delete an element X from the tree:
a. Find the node where the element resides.
b. If the node has no left and right children, then the pointer to that node from the parent is
changed to NULL and the node is freed of its memory.
c. If the node has only one child, then the parent of the node is made to point to the child of the
node and the node is freed.
d. If the node has both left and right children:
i. Look at the right subtree of the node (subtree rooted at the right child of the node).
ii. Find the Minimum there.
iii. Replace the key of the node to be deleted by the minimum element.
iv. Delete the minimum element.
5. To find an element X in the tree with root node T:
a. If the root node T is initially NULL, then the tree is empty. So return NULL and exit.
b. Take the element X and compare it with the root node. If X is less than the element found at
the root node, then repeat step 5 recursively with the new value of T as T->Left.
c. Take the element X and compare it with the root node. If X is more than the element found at
the root node, then repeat step 5 recursively with the new value of T as T->Right.
6. To find the minimum element in a tree with root node T:
a. If T is NULL return NULL.
b. Otherwise slide the value of T to T->Left until T->Left becomes NULL.
c. Return the value of T.
7. To find the maximum element in a tree with root node T:
a. If T is NULL return NULL.
b. Otherwise slide the value of T to T->Right until T->Right becomes NULL.
c. Return the value of T.
Tasks:
1. Compile and examine the program provided in file. Print the output in the space
provided.
Code:
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
TreeNode* insert(TreeNode* root, int val) {
if (!root) {
return new TreeNode(val);
}
if (val < root->data) {
root->left = insert(root->left, val);
} else if (val > root->data) {
root->right = insert(root->right, val);
}
return root;
}
bool search(TreeNode* root, int val) {
if (!root) {
return false;
}
if (root->data == val) {
return true;
} else if (val < root->data) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
void inorder(TreeNode* root) {
if (root) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
void preorder(TreeNode* root) {
if (root) {
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
}
void postorder(TreeNode* root) {
if (root) {
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
}
int main() {
TreeNode* root = nullptr;
int n;
cout << "Enter the number of elements to insert in the BST: ";
cin >> n;
cout << "Enter the elements: ";
for (int i = 0; i < n; i++) {
int val;
cin >> val;
root = insert(root, val);
}
cout << "Inorder Traversal: ";
inorder(root);
cout << endl;
cout << "Preorder Traversal: ";
preorder(root);
cout << endl;
cout << "Postorder Traversal: ";
postorder(root);
cout << endl;
int searchVal;
cout << "Enter a value to search in the BST: ";
cin >> searchVal;
if (search(root, searchVal)) {
cout << searchVal << " is found in the BST." << endl;
} else {
cout << searchVal << " is not found in the BST." << endl;
}
return 0;
}
Output:
2. Add the code find to minimum and maximum element in the tree.
Code:
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(0), right(0) {}
};
TreeNode* insert(TreeNode* root, int val) {
if (!root) {
return new TreeNode(val);
}
if (val < root->data) {
root->left = insert(root->left, val);
} else if (val > root->data) {
root->right = insert(root->right, val);
}
return root;
}
TreeNode* findMin(TreeNode* root) {
while (root && root->left) {
root = root->left;
}
return root;
}
TreeNode* findMax(TreeNode* root) {
while (root && root->right) {
root = root->right;
}
return root;
}
void inorder(TreeNode* root) {
if (root) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
int main() {
TreeNode* root = nullptr;
int n;
cout << "Enter the number of elements to insert in the BST: ";
cin >> n;
cout << "Enter the elements: ";
for (int i = 0; i < n; i++) {
int val;
cin >> val;
root = insert(root, val);
}
cout << "Inorder Traversal of the BST: ";
inorder(root);
cout << endl;
TreeNode* minNode = findMin(root);
TreeNode* maxNode = findMax(root);
if (minNode) {
cout << "Minimum value in the tree: " << minNode->data << endl;
} else {
cout << "Tree is empty, no minimum value." << endl;
}
if (maxNode) {
cout << "Maximum value in the tree: " << maxNode->data << endl;
} else {
cout << "Tree is empty, no maximum value." << endl;
}
return 0;
}
Output:
