(40 points) Implement a binary search tree class capable of storing integers. Th

Question

(40 points) Implement a binary search tree class capable of storing integers. There are two points of ambiguity: In the case where an inserted value is already present in the tree, insert to the left. In the case where a deleted value has two internal children, seek the minimum value in the right subtree to replace the deleted value (40 points) Using your binary search tree class, implement a program that transforms its input as follows Read a sequence of lines. Each line will have one of the following forms insert N or delete N where N is an integer value. Insert or delete that integer as indicated After reading all input, implement a function (e.g., level-print) to print the tree to the output level by-level. That is, print the root on one line, followed by the two nodes (from left to right) at level 1 on the second line, followed by the (up to) four nodes at level 2 on the next line, etc. For example, given the following input: nsert 5 insert 20 insert 3 insert 4 insert 9 delete 4 insert 7 The program will produce this output 3 20 7 9 Hint: the level-by-level output involves a breadth-first traversal of the tree, which can be implemented use a queue. You can use standard queue interface or library in java and c++

Explanation / Answer

Hi Student,

Please find the answer below :

  #include <iostream>
#include <queue>
using namespace std;
  
struct node
{
int key;
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->key = item;
temp->left = temp->right = NULL;
return temp;
}
  
// Iterative method to find height of Bianry Tree
void printLevelOrder(Node *root)
{
// Base Case
if (root == NULL) return;

// Create an empty queue for level order tarversal
queue<Node *> q;

// Enqueue Root and initialize height
q.push(root);

while (q.empty() == false)
{
// Print front of queue and remove it from queue
Node *node = q.front();
cout << node->data << " ";
q.pop();

/* Enqueue left child */
if (node->left != NULL)
q.push(node->left);

/*Enqueue right child */
if (node->right != NULL)
q.push(node->right);
}
}
  
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;
}
  
// Driver Program to test above functions
int main()
{
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
  
// print printLevelOrder traversal of the BST
printLevelOrder(root);
  
return 0;
}

Happy Learning :)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.