Solution and implementation for Q6 from Data Structures and Algorithms Laboratory (dsal).
#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = nullptr;
right = nullptr;
}
};
// Insert a new node in the Binary Search Tree (BST)
Node* insert(Node* root, int val) {
if (!root)
return new Node(val);
// If value is less than root, move to the left subtree
if (val < root->data)
root->left = insert(root->left, val);
// If value is greater, move to the right subtree
else
root->right = insert(root->right, val);
return root;
}
// Inorder Traversal (Left, Root, Right)
void inorder(Node* root) {
if (!root)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
// Find the height of the binary tree
int findHeight(Node* root) {
if (!root)
return 0;
int leftHeight = findHeight(root->left);
int rightHeight = findHeight(root->right);
return 1 + max(leftHeight, rightHeight);
}
// Find the minimum value in the binary tree
int findMin(Node* root) {
if (!root)
return -1;
while (root->left)
root = root->left;
return root->data;
}
// Mirror the binary tree (swap left and right subtrees)
void mirror(Node* root) {
if (!root)
return;
swap(root->left, root->right);
mirror(root->left);
mirror(root->right);
}
// Search for a value in the binary search tree
bool search(Node* root, int val) {
if (!root)
return false;
if (root->data == val)
return true;
if (val < root->data)
return search(root->left, val);
return search(root->right, val);
}
int main() {
Node* root = nullptr;
int total, val;
// Input total number of elements to be inserted
cout << "Enter total number of elements: ";
cin >> total;
// Insert elements into the BST
for (int i = 0; i < total; i++) {
cout << "Enter value " << i + 1 << ": ";
cin >> val;
root = insert(root, val);
}
// Inorder traversal of the BST
cout << "Inorder traversal of the BST: ";
inorder(root);
cout << endl;
// Insert a new node and print the inorder traversal
int newNode;
cout << "Enter a value to insert: ";
cin >> newNode;
root = insert(root, newNode);
cout << "Inorder traversal after inserting " << newNode << ": ";
inorder(root);
cout << endl;
// Find and print the height of the tree
int height = findHeight(root);
cout << "Height (Number of nodes in the longest path): " << height << endl;
// Find and print the minimum value in the BST
int minValue = findMin(root);
cout << "Minimum value in the BST: " << minValue << endl;
// Search for a value in the BST
int searchValue;
cout << "Enter a value to search: ";
cin >> searchValue;
bool isFound = search(root, searchValue);
cout << "Search for " << searchValue << ": " << (isFound ? "Found" : "Not Found") << endl;
// Mirror the tree and print the inorder traversal
mirror(root);
cout << "Inorder traversal after mirroring the tree: ";
inorder(root);
cout << endl;
return 0;
}