slove the question in C++.Show each output clearly.

Question

int main(){

// Create a binary search tree

// Insert nodes: 10, 5, 15, 2, 7, 13, 6, 8, 11, 17

// Print the tree

// Print tree height

// Print the minimum value in the tree

// Print the maximum value in the tree

// Print the number of nodes in the tree

// Manually print the nodes at each level (see example below)

cout << "Level 0: 10" << endl;

// Delete exactly two nodes to make the tree full and complete

// Print tree again

// Insert 8 more nodes but make sure that tree becomes full and complete

// Print tree again

// Delete all the nodes in the tree

// Print the tree again

}

Answer 1

#include <iostream>

#include <queue>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

Node(int val) : data(val), left(NULL), right(NULL) {}

};

class BST {

private:

Node* root;

Node* insert(Node* node, int val) {

if (node == NULL) return new Node(val);

if (val < node->data) node->left = insert(node->left, val);

else if (val > node->data) node->right = insert(node->right, val);

return node;

}

Node* findMin(Node* node) {

while (node->left != NULL) node = node->left;

return node;

}

Node* deleteNode(Node* node, int val) {

if (node == NULL) return NULL;

if (val < node->data) node->left = deleteNode(node->left, val);

else if (val > node->data) node->right = deleteNode(node->right, val);

else {

if (node->left == NULL) {

Node* temp = node->right;

delete node;

return temp;

} else if (node->right == NULL) {

Node* temp = node->left;

delete node;

return temp;

}

Node* temp = findMin(node->right);

node->data = temp->data;

node->right = deleteNode(node->right, temp->data);

}

return node;

}

void inorder(Node* node) {

if (node == NULL) return;

inorder(node->left);

cout << node->data << " ";

inorder(node->right);

}

int height(Node* node) {

if (node == NULL) return -1;

return 1 + max(height(node->left), height(node->right));

}

int countNodes(Node* node) {

if (node == NULL) return 0;

return 1 + countNodes(node->left) + countNodes(node->right);

}

int findMinValue(Node* node) {

if (node == NULL) return -1;

while (node->left != NULL) node = node->left;

return node->data;

}

int findMaxValue(Node* node) {

if (node == NULL) return -1;

while (node->right != NULL) node = node->right;

return node->data;

}

void deleteAll(Node* node) {

if (node == NULL) return;

deleteAll(node->left);

deleteAll(node->right);

delete node;

}

public:

BST() : root(NULL) {}

void insert(int val) {

root = insert(root, val);

}

void deleteNode(int val) {

root = deleteNode(root, val);

}

void printTree() {

if (root == NULL) {

cout << "Tree is empty" << endl;

return;

}

cout << "Tree (in-order): ";

inorder(root);

cout << endl;

}

void printLevelByLevel() {

if (root == NULL) return;

queue<Node*> q;

q.push(root);

int level = 0;

while (!q.empty()) {

int size = q.size();

cout << "Level " << level << ": ";

for (int i = 0; i < size; i++) {

Node* node = q.front();

q.pop();

cout << node->data;

if (i < size - 1) cout << ", ";

if (node->left) q.push(node->left);

if (node->right) q.push(node->right);

}

cout << endl;

level++;

}

}

int getHeight() {

return height(root);

}

int getMin() {

return findMinValue(root);

}

int getMax() {

return findMaxValue(root);

}

int getNodeCount() {

return countNodes(root);

}

void deleteAll() {

deleteAll(root);

root = NULL;

}

};

int main() {

BST tree;

// Create a binary search tree

// Insert nodes: 10, 5, 15, 2, 7, 13, 6, 8, 11, 17

cout << "=== Initial Tree ===" << endl;

tree.insert(10);

tree.insert(5);

tree.insert(15);

tree.insert(2);

tree.insert(7);

tree.insert(13);

tree.insert(6);

tree.insert(8);

tree.insert(11);

tree.insert(17);

// Print the tree

tree.printTree();

// Print tree height

cout << "Tree height: " << tree.getHeight() << endl;

// Print the minimum value in the tree

cout << "Minimum value: " << tree.getMin() << endl;

// Print the maximum value in the tree

cout << "Maximum value: " << tree.getMax() << endl;

// Print the number of nodes in the tree

cout << "Number of nodes: " << tree.getNodeCount() << endl;

// Manually print the nodes at each level

cout << "\nNodes by level:" << endl;

tree.printLevelByLevel();

// Delete exactly two nodes to make the tree full and complete

// Delete 6 and 8 (leaf nodes that prevent tree from being complete)

cout << "\n=== After deleting 6 and 8 ===" << endl;

tree.deleteNode(6);

tree.deleteNode(8);

tree.printTree();

cout << "Tree height: " << tree.getHeight() << endl;

cout << "Number of nodes: " << tree.getNodeCount() << endl;

cout << "\nNodes by level:" << endl;

tree.printLevelByLevel();

// Insert 8 more nodes to make tree full and complete

// To make a full and complete tree with 16 nodes (perfect tree of height 3)

// Current nodes: 10, 5, 15, 2, 7, 13, 11, 17

// Need to add: 1, 3, 9, 12, 14, 16, 18, 4

cout << "\n=== After inserting 8 more nodes (1, 3, 4, 9, 12, 14, 16, 18) ===" << endl;

tree.insert(1);

tree.insert(3);

tree.insert(4);

tree.insert(9);

tree.insert(12);

tree.insert(14);

tree.insert(16);

tree.insert(18);

tree.printTree();

cout << "Tree height: " << tree.getHeight() << endl;

cout << "Number of nodes: " << tree.getNodeCount() << endl;

cout << "\nNodes by level:" << endl;

tree.printLevelByLevel();

// Delete all the nodes in the tree

cout << "\n=== After deleting all nodes ===" << endl;

tree.deleteAll();

tree.printTree();

return 0;

}