/*
Beginning with an empty binary search tree, Construct binary search tree by inserting the
values in the order given. After constructing a binary tree - i. Insert new node, ii. Find
number of nodes in longest path from root, iii. Minimum data value found in the tree, iv.
Change a tree so that the roles of the left and right pointers are swapped at every node, v.
Search a value
*/
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node *root = nullptr;
int countNodes = 0;
class BST {
public:
void create();
void insert(Node *current, Node *newNode);
void inorderTraversal(Node *current);
void preorderTraversal(Node *current);
void postorderTraversal(Node *current);
void search(Node *current, int key);
int height(Node *current);
void findMin(Node *current);
void mirror(Node *current);
BST() {
root = nullptr;
countNodes = 0;
}
};
void BST::create() {
char ans;
do {
Node *temp = new Node;
cout << "Enter the data: ";
cin >> temp->data;
temp->left = temp->right = nullptr;
if (root == nullptr) {
root = temp;
} else {
insert(root, temp);
}
countNodes++;
cout << "Do you want to insert more values (y/n)? ";
cin >> ans;
cout << endl;
} while (ans == 'y');
cout << "The total number of nodes are: " << countNodes << endl;
}
void BST::insert(Node *current, Node *newNode) {
if (newNode->data > current->data) {
if (current->right == nullptr) {
current->right = newNode;
} else {
insert(current->right, newNode);
}
} else {
if (current->left == nullptr) {
current->left = newNode;
} else {
insert(current->left, newNode);
}
}
}
void BST::inorderTraversal(Node *current) {
if (current != nullptr) {
inorderTraversal(current->left);
cout << current->data << "\t";
inorderTraversal(current->right);
}
}
void BST::preorderTraversal(Node *current) {
if (current != nullptr) {
cout << current->data << "\t";
preorderTraversal(current->left);
preorderTraversal(current->right);
}
}
void BST::postorderTraversal(Node *current) {
if (current != nullptr) {
postorderTraversal(current->left);
postorderTraversal(current->right);
cout << current->data << "\t";
}
}
void BST::search(Node *current, int key) {
while (current != nullptr) {
if (key == current->data) {
cout << "Key FOUND\n";
return;
}
if (key > current->data) {
current = current->right;
} else {
current = current->left;
}
}
cout << "Key NOT FOUND\n";
}
int BST::height(Node *current) {
if (current == nullptr) {
return 0;
}
int leftHeight = height(current->left);
int rightHeight = height(current->right);
return 1 + max(leftHeight, rightHeight);
}
void BST::findMin(Node *current) {
if (current == nullptr) {
cout << "Tree is empty.\n";
return;
}
while (current->left != nullptr) {
current = current->left;
}
cout << "The minimum element is: " << current->data << endl;
}
void BST::mirror(Node *current) {
if (current != nullptr) {
mirror(current->left);
mirror(current->right);
Node *temp = current->left;
current->left = current->right;
current->right = temp;
}
}
int main() {
BST tree;
int choice, key;
char cont;
do {
cout << "\n1) Insert new node\n2) Number of nodes in longest path\n3) Minimum\n4) Mirror\n5) Search\n6) Inorder\n7) Preorder\n8) Postorder\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
tree.create();
break;
case 2:
cout << "\nNumber of nodes in longest path: " << tree.height(root) << endl;
break;
case 3:
tree.findMin(root);
break;
case 4:
tree.mirror(root);
cout << "\nThe mirror of the tree (inorder traversal): ";
tree.inorderTraversal(root);
cout << endl;
break;
case 5:
cout << "\nEnter the key to search: ";
cin >> key;
tree.search(root, key);
break;
case 6:
cout << "\n*************** INORDER ***************\n";
tree.inorderTraversal(root);
cout << endl;
break;
case 7:
cout << "\n*************** PREORDER ***************\n";
tree.preorderTraversal(root);
cout << endl;
break;
case 8:
cout << "\n*************** POSTORDER ***************\n";
tree.postorderTraversal(root);
cout << endl;
break;
default:
cout << "Invalid choice. Please try again.\n";
}
cout << "\nDo you want to continue (y/n)? ";
cin >> cont;
} while (cont == 'y');
return 0;
}
