You will need to implement lookup, which returns a boolean indicating whether th
ID: 3742983 • Letter: Y
Question
You will need to implement lookup, which returns a boolean indicating whether the target was found, insert, which adds an item to the BST, remove, which removes an item from the BST, and pre-, in-, post-, and level-order traversals which prints the tree in the appropriate order. For example, in C++, the function headers would be the following:
Input Format
The first line of the input will be an integer n indicating how many commands follow it. The next n lines will consist of one of 7 commands ("insert", "lookup", "delete", "preorder", "postorder", "levelorder", and "inorder"). The commands "insert", "lookup", and "delete" will be followed by a space and an integer to perform the command on. Note that the argument to "delete" may not be in the BST, in which case you should do nothing. At the end of the input there will be a blank line. Your program should initialize an empty BST and perform the commands given by the input, in sequence, on it. For example, valid input might be:
Constraints
1 <= n <= 100 (You will be asked to perform between 1 and 100 commands, inclusive, on your BST, per test case.) You can also assume there will be no invalid input. You can assume the BST will consist only of positive integers with no duplicates.
Output Format
For the "lookup" command, print the line "0" if the target is not found and the line "1" if it is found. For the traversal ("preorder", "postorder", "inorder", "levelorder") commands, print a line containing the space-separated traversal (the line will end in a space). For the "insert" and "delete" commands, print nothing. For example, the appropriate output for the sample input is:
Sample Input 0
Sample Output 0
Here's what I have so far please help
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node *left;
Node *right;
};
class BST {
Node *root;
public:
BST() {
root = nullptr;
}
bool lookup(int target) {
}
void insert(int data) {
}
void preOrder() {
}
void postOrder() {
}
void inOrder() {
}
void levelOrder() {
}
void takeOut(int target) {
}
};
int main()
{
int n;
cin >> n;
cin.ignore();
for (int i = 0; i < n; i++) {
string rawInput;
vector<string> words;
string word = "";
getline(cin, rawInput);
for (int j = 0; j < rawInput.size(); j++) {
if (rawInput[j] == ' ') {
words.push_back(word);
word = "";
} else {
word = word + rawInput[j];
if (j == rawInput.size()-1) {
words.push_back(word);
}
}
}
// if (words[0] == "insert") {
// insert(words[1]);
// } else if (words[0] == "lookup") {
// lookup(words[1]);
// } else if (words[0] == "delete") {
// takeOut(words[1]);
// } else if (words[0] == "prorder") {
// preOrder();
// } else if (words[0] == "postorder") {
// postOrder();
// } else if (words[0] == "levelorder") {
// levelOrder();
// } else if (words[0] == "inorder") {
// inOrder();
// }
}
}
Explanation / Answer
#include <iostream>
#include <vector>
#include <sstream>
#include <queue>
using namespace std;
// Defines a structure to create a Node
struct Node
{
// Data member to store data
int data;
// Pointer to left child
Node *left;
// Pointer to right child
Node *right;
};// End of structure Node
// Class BST definition
class BST
{
// Creates an object of structure for root node
Node *root;
public:
// Default constructor
BST()
{
root = NULL;
}// End of default constructor
// Helper function to search a number in BST
// Returns 1 if found
int lookupHelper(int target, Node *p)
{
// Checks if current node is not null
if (p != NULL)
{
// Returns 1 if match found
if(p->data == target)
return 1;
// Moves towards left
lookupHelper(target, p->left);
// Moves towards right
lookupHelper(target, p->right);
}// End of if
}// End of function
// Function to return true if target is found in BST otherwise returns false
bool lookup(int target)
{
// Calls the function to check the target number in BST
// Checks if return value of the function is 1 then returns true
if(lookupHelper(target, root) == 1)
return true;
// Otherwise returns false
else
return false;
}// End of function
// Function to insert a node
void insert(int data)
{
// Create a new node
Node *newptr = new Node;
// Stores the data in node
newptr->data = data;
// Set the left and right pointer of the node to null
newptr->left = NULL;
newptr->right = NULL;
// Checks if root is null then it is the first node
if (root == NULL)
{
// Set the root to new node
root = newptr;
}// End of if condition
// Otherwise
else
{
// Create a temporary pointer of type node and point to root
Node *p = root;
// Create a parent pointer pointer of type node and assign null to it
Node *parent = NULL;
// Find the right location for the new node
// Loops till leaf node and node pointing to data is not equals to the inserted number
while ((p != NULL) && (p->data != data))
{
// Checks if the number to insert is less than current node data
if (data < p->data)
{
// Set the current node as parent
parent = p;
// Current node is pointing to its left
p = p->left;
}// End of if condition
// Otherwise number is greater than the current node data
else
{
// Set the current node as parent
parent = p;
// Current node is pointing to its right
p = p->right;
}// End of else
}// End of while
// If the element is not in the BST
if (p == NULL)
{
// Checks if the number to insert is less than current node data
if (data < parent->data)
// Parent node left is pointing to new node
parent->left = newptr;
// Otherwise number is greater than the current node data
else
// Parent node right is pointing to new node
parent->right = newptr;
}// End of if
// Otherwise node is already available
else
cout << "node duplicate!" << endl;
}// End of else
}// End of function
// Helper function for pre order traversal
void preOrderHelper(Node *p)
{
// Traverse: Root, Left, Right
// Checks if current node is not null
if (p != NULL)
{
// Displays the root node value
cout << p->data << " ";
// Moves towards left
preOrderHelper(p->left);
// Moves towards right
preOrderHelper(p->right);
}// End of if
}// End of function
// Function to call helper function by passing root node to it
// For pre order traversal
void preOrder()
{
preOrderHelper(root);
}// End of function
// Helper function to perform post order traversal
void postOrderHelper(Node *p)
{
// Traverse: Left, Right, Root
// Checks if current node is not null
if (p != NULL)
{
// Moves towards left
postOrderHelper(p->left);
// Moves towards right
postOrderHelper(p->right);
// Displays the root node value
cout << p->data << " ";
}// End of if
}// End of function
// Function to call helper function by passing root node to it
// For post order traversal
void postOrder()
{
postOrderHelper(root);
}// End of function
// Function to call helper function by passing root node to it
// For in order traversal
void inOrder()
{
inOrderHelper(root);
}// End of function
// Helper function to perform in order traversal
void inOrderHelper(Node *p)
{
// Traverse: Left, Root, Right
// Checks if current node is not null
if (p != NULL)
{
// Moves towards left
inOrderHelper(p->left);
// Displays the root node value
cout << p->data << " ";
// Moves towards right
inOrderHelper(p->right);
}// End of if
}// End of function
// Function to call helper function by passing root node to it
// For level order traversal
levelOrder()
{
levelOrderHelper(root);
}// End of function
// Helper function for level order traversal
void levelOrderHelper(Node *p)
{
// Checks if root node is NULL then return
// BST is empty
if (p == NULL)
return;
// Create an empty queue for level order trarversal
queue<Node *> que;
// Inserts root and initialize height
que.push(root);
while (1)
{
// nodeCount (queue size) indicates number of nodes at current lelvel.
int nodeCounter = que.size();
// Checks if node counter is zero then stop
if (nodeCounter == 0)
break;
// Delete all nodes of current level and insert all nodes of next level
// Checks if counter is greater than zero
while (nodeCounter > 0)
{
// Stores the front node in temp node
Node *temp = que.front();
// Displays the data
cout << temp->data << " ";
que.pop();
// Checks if left node is not NULL
if (temp->left != NULL)
// Inserts left node
que.push(temp->left);
// Checks if right node is not NULL
if (temp->right != NULL)
// Inserts right node
que.push(temp->right);
// Decreases the counter by one
nodeCounter--;
}// End of while loop
cout << endl;
}// End of while
}// End of function
// Function to delete a node
void takeOut(int target)
{
// Create a temporary pointer p of type node and point to root
Node *p = root;
// Create a temporary pointer parent and assign null to it
Node *parent = NULL;
// Find the correct location for the new node to delete
// Loops till leaf node and node pointing to data is not equals to the delete number
while ((p != NULL) && (p->data != target))
{
// Checks if the number to insert is less than current node data
if (target < p->data)
{
// Set the current node as parent
parent = p;
// Current node is pointing to its left
p = p->left;
}// End of if
// Otherwise number is greater than the current node data
else
{
// Set the current node as parent
parent = p;
// Current node is pointing to its right
p = p->right;
}// End of else
}// End of while loop
// Case 1
if (p->left == NULL && p->right == NULL)
{
// Checks if the number to delete is less than current node data
if (target < parent->data)
// Set the parent node left to null
parent->left = NULL;
// Otherwise
else
// Set the parent node right to null
parent->right = NULL;
delete p;
}// End of if
// Case 2
else if (p->left != NULL && p->right == NULL)
{
// Checks if the number to delete is less than current node data
if (target < parent->data)
// Set the parent node left to current node left
parent->left = p->left;
// Otherwise
else
// Set the parent node right to current node left
parent->right = p->left;
delete p;
}// End of else if
//case 2
else if (p->left == NULL && p->right != NULL)
{
// Checks if the number to delete is less than current node data
if (target < parent->data)
// Set the parent node left to current node right
parent->left = p->right;
// Otherwise
else
// Set the parent node right to current node right
parent->right = p->right;
delete p;
}// End of else if
// Case 3
else
{
// Calls the function to find the minimum node from the right
int min_of_right_child = findmin(p->right);
// Call the function Remove the node min_of_right_child
takeOut(min_of_right_child);
// Set the current node data to min_of_right_child
p->data = min_of_right_child;
}// End of else
}// End of function
// Function to find the node having minimum value
int findmin(Node *p)
{
// Loops till left is null
while (p->left != NULL)
// Move towards left
p = p->left;
// Returns the data
return p->data;
}// End of function
};
int main()
{
// Creates a pointer of class BST
BST *t1 = new BST();
int n;
cin >> n;
cin.ignore();
for (int i = 0; i < n; i++)
{
string rawInput;
int number = 0;
vector<string> words;
string word = "";
getline(cin, rawInput);
for (int j = 0; j < rawInput.size(); j++)
{
if (rawInput[j] == ' ')
{
words.push_back(word);
word = "";
}
else
{
word = word + rawInput[j];
if (j == rawInput.size()-1)
{
words.push_back(word);
}
}
}
if (words[0] == "insert")
{
// object from the class stringstream
stringstream data(words[1]);
// The object has the value 12345 and stream
// it to the integer number
data >> number;
t1->insert(number);
}
else if (words[0] == "lookup")
{
// object from the class stringstream
stringstream data(words[1]);
// The object has the value 12345 and stream
// it to the integer number
data >> number;
cout<<t1->lookup(number)<<endl;
}
else if (words[0] == "delete")
{
// object from the class stringstream
stringstream data(words[1]);
// The object has the value 12345 and stream
// it to the integer number
data >> number;
t1->takeOut(number);
}
else if (words[0].compare("preorder") == 0)
{
t1->preOrder();
cout<<endl;
}
else if (words[0] == "postorder")
{
t1->postOrder();
cout<<endl;
}
else if (words[0] == "levelorder")
{
t1->levelOrder();
}
else if (words[0] == "inorder")
{
t1->inOrder();
cout<<endl;
}
else
cout<<" Invalid command!";
}
}
Sample Output:
20
lookup 5
0
insert 5
lookup 5
1
insert 18
insert 3
insert 12
preorder
5 3 18 12
insert 19
lookup 20
0
delete 3
lookup 3
0
postorder
12 19 18 5
insert 25
insert 6
insert 1
inorder
1 5 6 12 18 19 25
lookup 18
1
delete 18
lookup 18
0
postorder
1 6 12 25 19 5
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.