Submit a program that implements a BST(Binary Search Tree). Specifically, write

ID: 3906019 • Letter: S

Question

Submit a program that implements a BST(Binary Search Tree). Specifically, write functions that:

Insert a node given an integer into the tree.

Delete the node in the tree given an integer. If the node does not exist in the tree, then let the user know.

Print the values in the tree in ascending order.

Print the tree using parenthetical notation.

Given an integer, return the node pointer for the node that has that integer as an attribute.

Display just the smallest value in the BST.

Display just the largest value in the BST.

If you decide to provide your own main function, then it should present a menu allowing me to execute any one of the five functions above. The menu should loop until I choose the option to quit the program.

Include all the files needed if you choose to use header files.

c++, Please post only working code, and output if possible.

Explanation / Answer

Hello Student!

Happy to help you!

******************* Here goes the solution****************

#include<iostream>

using namespace std;

struct node {

int data;

struct node *left, *right;

};

// A utility function to create a new BST node

struct node *newNode(int item)

{

struct node *temp = (struct node *)malloc(sizeof(struct node));

temp->data = item;

temp->left = temp->right = NULL;

return temp;

}

// Inorder ascending traversal

void inorder(struct node *root) {

if (root != NULL) {

inorder(root->left);

cout << root->data << " ";

inorder(root->right);

}

// Insert into root node

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

root->right = insert(root->right, data);

return root;

}

// maximum value

struct node* max(node* root) {

if(root == NULL) {

return NULL;

}

if(root->right == NULL) {

return root;

}

return max(root->right);

}

// minimum value

struct node * min(node* node) {

struct node* curr = node;

// leftmost element is the smallest

while (curr->left != NULL) {

curr = curr->left;

}

return curr;

}

// deletion of a node

struct node* del_node(struct node* root, int data)

{

// base case

if (root == NULL) {

return root;

}

// if data is smaller than root

// traverse in left part of the tree

if (data < root->data) {

root->left = del_node(root->left, data);

} else if (data > root->data) { // if it is greater traverse in right part

root->right = del_node(root->right, data);

} else {

// If data is smae

if (root->left == NULL) {

struct node *tmp = root->right;

free(root);

return tmp;

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

struct node *tmp = root->left;

free(root);

return tmp;

}

struct node* temp = min(root->right);

root->data = temp->data;

root->right = del_node(root->right, temp->data);

}

return root;

}

int main() {

struct node *root = NULL;

char ch = 'y';

cout << "1 Insert ";

cout << "2 Delete ";

cout << "3 Print ascending values ";

cout << "4 Display the smallest value ";

cout << "5 Display the largest value ";

while (ch == 'y' || ch == 'Y') {

int option;

cin >> option;

switch (option) {

case 1 : cout << "Enter node value :";

int val;

cin >> val;

root = insert(root, val);

cout << val << " is Inserted! ";

break;

case 2 :

int value;

cin >> value;

del_node(root, value);

break;

case 3 : cout << "The ascending values :";

inorder(root);

break;

case 4 : cout << "The smallest value :" << min(root)->data << endl;

break;

case 5 : cout << "The largest value :" << max(root)->data << endl;

break;

default : cout << "No option selected! ";

break;

}

cout << "Want to perform any option? (Y/N) :";

cin >> ch;

}

return 0;

}

****************Ends here************

Test Case :

1 Insert

2 Delete

3 Print ascending values

4 Display the smallest value

5 Display the largest value

1 50

Enter node value :50 is Inserted!