CS 3358 BST

In this assignment, you are asked to implement several functions in a Binary Search Tree (BST) class called MyBST in bst.cpp. The places you need to fill out in the code are marked by // TODO.

• Implement the function FindHelper(). This function should be a recursive function.
• Implement the function InsertHelper(). This function should be a recursive function. If the input value turns out to be an existing one, your function should print out the following message without adding the duplicate value into the BST, where < value> should be the duplicate value (see Test Case).

< value> already exits. No new node has been inserted.

If you want to implement the function without passing a pointer by reference, you need to use the following Insert() function instead of the given one. Note that it is the 'commented out' function in bst.cpp.

void MyBST::Insert(int x) {
if (root != NULL) {
InsertHelper(root, x);
} else {
root = new TreeNode;
root->value = x;
root->right = NULL;
root->left = NULL;
}
}

• Implement the functions Preorder(), Postorder(), and Inorder(), which are used in the functions PreorderTraversal(), PostorderTraversal(), and InorderTraversal(), respectively. They should be recursive functions.

Test Case:

Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 36
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 20
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 57
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 18
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 44
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 76
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 93
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 120
Invalid input value (120) !
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: 44
44 already exits. No new node has been inserted.
Inserting a new node....
Please enter an integer between 0 and 99 as a value to insert, or enter -1 to
stop inserting and see the resulting tree: -1
Preorder Traversal: 36 20 18 57 44 76 93
Postorder Traversal: 18 20 44 93 76 57 36
Inorder Traversal: 18 20 36 44 57 76 93
Searching a value....
Please enter an integer between 0 and 99 as a value to search, or enter -1 to
stop searching: 57
57 is in this BST.
Searching a value....
Please enter an integer between 0 and 99 as a value to search, or enter -1 to
stop searching: 20
20 is in this BST.
Searching a value....
Please enter an integer between 0 and 99 as a value to search, or enter -1 to
stop searching: 76
76 is in this BST.
Searching a value....
Please enter an integer between 0 and 99 as a value to search, or enter -1 to
stop searching: 55
55 is not in this BST.
Searching a value....
Please enter an integer between 0 and 99 as a value to search, or enter -1 to
stop searching: 25
25 is not in this BST.
Searching a value....
Please enter an integer between 0 and 99 as a value to search, or enter -1 to
stop searching: -1

Starter Code:

#include < iostream>

using namespace std;

struct TreeNode
{
int value;
TreeNode* left;
TreeNode* right;
};

class MyBST
{
public:
MyBST() { root = NULL; }
~MyBST();
bool Find(int x);
void Insert(int x);
void PreorderTraversal();
void PostorderTraversal();
void InorderTraversal();

private:
TreeNode* root;

void FreeHelper(TreeNode* node);
bool FindHelper(TreeNode* node, int x);
//void InsertHelper(TreeNode* node, int x); // use this one if you want to implement InsertHelper without passing a pointer by reference.
void InsertHelper(TreeNode*& node, int x);
void Preorder(TreeNode* node);
void Postorder(TreeNode* node);
void Inorder(TreeNode* node);
};

MyBST::~MyBST()
{
FreeHelper(root);
}

void MyBST::FreeHelper(TreeNode* node)
{
if (node != NULL)
{
FreeHelper(node->left);
FreeHelper(node->right);
delete node;
}
}

bool MyBST::FindHelper(TreeNode* node, int x)
{
// TODO
}


bool MyBST::Find(int x)
{
return FindHelper(root, x);
}

//void MyBST::InsertHelper(TreeNode* node, int x) { // use this one if you want to implement InsertHelper without passing a pointer by reference.
void MyBST::InsertHelper(TreeNode*& node, int x)
{
// TODO
}

// use this one if you want to implement InsertHelper without passing a pointer by reference.
/*
void MyBST::Insert(int x) {
if (root != NULL) {
InsertHelper(root, x);
} else {
root = new TreeNode;
root->value = x;
root->right = NULL;
root->left = NULL;
}
}
*/

void MyBST::Insert(int x)
{
InsertHelper(root, x);
}


void MyBST::Preorder(TreeNode* node)
{
// TODO
}

void MyBST::PreorderTraversal()
{
Preorder(root);
cout << endl;
}


void MyBST::Postorder(TreeNode* node)
{
// TODO
}

void MyBST::PostorderTraversal()
{
Postorder(root);
cout << endl;
}


void MyBST::Inorder(TreeNode* node)
{
// TODO
}

void MyBST::InorderTraversal()
{
Inorder(root);
cout << endl;
}


int main()
{
MyBST test_tree;

int user_input = 0;

while (user_input != -1)
{
cout << "Inserting a new node...." << endl;
cout << "Please enter an integer between 0 and 99 as a value to insert, ";
cout << "or enter -1 to stop inserting and see the resulting tree: ";
cin >> user_input;
if (user_input >= 0 && user_input <= 99)
test_tree.Insert(user_input);
else if (user_input != -1)
cout << "Invalid input value (" << user_input << ") !" << endl;
}

cout << "Preorder Traversal: ";
test_tree.PreorderTraversal();
cout << "Postorder Traversal: ";
test_tree.PostorderTraversal();
cout << "Inorder Traversal: ";
test_tree.InorderTraversal();

user_input = 0;

while (user_input != -1) {
cout << "Searching a value...." << endl;
cout << "Please enter an integer between 0 and 99 as a value to search, ";
cout << "or enter -1 to stop searching: ";
cin >> user_input;

if (user_input >= 0 && user_input <= 99) {
if (test_tree.Find(user_input))
cout << user_input << " is in this BST." << endl;
else {
cout << user_input << " is not in this BST." << endl;
}
}
else if (user_input != -1)
cout << "Invalid input value (" << user_input << ") !" << endl;
}

return 0;
}