1. (25 pts) Implement the insert method for binary search trees. Do not insert duplicate values. 2. (15 pts) Implement the search method for binary search trees. 3. (15 pts) Implement isBST, a method for checking whether or not a tree is a binary search tree. 4. (10 pts) Implement the pre-order traversal method for binary search trees.

All of this should be implemented in the below code, in C++, without changing any of the parameters or functions as they are laid out.

#include #include #include #include "BST.h"

BST::BST(){ }

BST::~BST(){}

std::shared_ptr BST::search(int target){ return nullptr; }

std::shared_ptr BST::search(std::shared_ptr n, int target){ return nullptr; }

std::shared_ptr BST::minimum(){ return nullptr; }

std::shared_ptr BST::minimum(std::shared_ptr n){ return nullptr; }

std::shared_ptr BST::maximum(){ return nullptr; }

std::shared_ptr BST::maximum(std::shared_ptr n){ return nullptr; }

void BST::insertValue(int val){ }

std::shared_ptr BST::insertValue(std::shared_ptr n, int val){ return nullptr; }

void BST::deleteValue(int val){ }

std::shared_ptr BST::deleteValue(std::shared_ptr n, int val){ return nullptr; }

bool BST::isBST(std::shared_ptr n){ return false; }

bool BST::isBST(std::shared_ptr n, int low, int high){ return false; }

void BST::preOrder(std::shared_ptr n, std::vector> &order){ }

void BST::inOrder(std::shared_ptr n, std::vector> &order){ }

void BST::postOrder(std::shared_ptr n, std::vector> &order){ }

The code above is meant to be grouped together with the below code:

BST.h:

// CSCI 311 - Spring 2023 // Lab 3 BST header // Author: Carter Tillquist

#ifndef BST_H #define BST_H

#include #include #include "Node.h"

class BST{ public: std::shared_ptr root; int size; Node* left; Node* right; Node* data;

BST(); ~BST();

std::shared_ptr search(int); std::shared_ptr search(std::shared_ptr, int);

std::shared_ptr minimum(); std::shared_ptr minimum(std::shared_ptr); std::shared_ptr maximum(); std::shared_ptr maximum(std::shared_ptr);

void insertValue(int); std::shared_ptr insertValue(std::shared_ptr, int); void deleteValue(int); std::shared_ptr deleteValue(std::shared_ptr, int);

bool isBST(std::shared_ptr); bool isBST(std::shared_ptr, int, int); void preOrder(std::shared_ptr, std::vector>&); void inOrder(std::shared_ptr, std::vector>&); void postOrder(std::shared_ptr, std::vector>&); };

#endif

Node.cpp:

// CSCI 311 - Spring 2023 // Node Class // Author: Carter Tillquist

#include "Node.h"

Node::Node(){ value = 0; left = nullptr; right = nullptr; }

Node::Node(int v){ value = v; left = nullptr; right = nullptr; }

Node::~Node(){}

Node.h

// CSCI 311 - Spring 2023 // Node Header // Author: Carter Tillquist

#ifndef NODE_H #define NODE_H

#include

class Node{ public: int value; Node* left; Node* right; Node* data; Node(); Node(int); ~Node(); };

#endif

BSTDriver.cpp

// CSCI 311 - Spring 2023 // Lab 3 - BST Driver // Author: Carter Tillquist

#include #include #include #include "BST.h" using namespace std;

void printVector(const vector>& v); void runSearch(std::shared_ptr T); void runInsert(std::shared_ptr T); void runDelete(std::shared_ptr T);

/************************************************** * Simple main to test Binary Search Tree methods * * ************************************************/ int main() { std::shared_ptr T(new BST());

int operation; cin >> operation;

while (operation > 0) { vector> order; switch (operation) { case 1: // search cout << "SEARCH FOR "; runSearch(T); break; case 2: // insert cout << "INSERT "; runInsert(T); break; case 3: // delete cout << "DELETE "; runDelete(T); break; case 4: // preorder cout << "PREORDER" << endl; T->preOrder(T->root, order); printVector(order); break; case 5: // inorder cout << "INORDER" << endl; T->inOrder(T->root, order); printVector(order); break; case 6: // postorder cout << "POSTORDER" << endl; T->postOrder(T->root, order); printVector(order); break; case 7: // minimum cout << "MINIMUM" << endl; cout << T->minimum()->value << endl; break; case 8: // maximum cout << "MAXIMUM" << endl; cout << T->maximum()->value << endl; break; case 9: // is BST cout << "IS BST" << endl; cout << T->isBST(T->root) << endl; break; default: break; } cin >> operation; }

return 0; }

/***************************************************************** * Print the values of nodes in a vector * * v - const vector> & - a vector of Nodes * * ***************************************************************/ void printVector(const vector>& v) { for (int i = 0; i < v.size(); i++) { cout << v[i]->value << " "; } cout << endl; }

/******************************************************************************************* * Given a BST, get a value to search for from the console and apply the BST search method * * T - std::shared_ptr - a Binary Search Tree * * *****************************************************************************************/ void runSearch(std::shared_ptr T) { int target; cin >> target; cout << target << endl; std::shared_ptr n = T->search(target); if (n) { cout << n->value << endl; } else { cout << "Not found" << endl; } }

/******************************************************************** * Given a BST, get a value from the console and add it to the tree * * T - std::shared_ptr - a Binary Search Tree * * ******************************************************************/ void runInsert(std::shared_ptr T) { int newVal; cin >> newVal; cout << newVal << endl; T->insertValue(newVal); }

/************************************************************************************** * Given a BST, get a value from the console and remove it from the tree if it exists * * T - std::shared_ptr - a Binary Search Tree * * ************************************************************************************/ void runDelete(std::shared_ptr T) { int remove; cin >> remove; cout << remove << endl; T->deleteValue(remove); }