C++ Recursion Assigment. (This is the FOURTH time I pose this. PLEASE READ CAREFULLY)

1. Edit the binarySearchTree.h file so that the main.cpp file runs correctly. USE RECURSION to implement the methods. NO LOOPS.

DO NOT use any STL libraries.

I had someone use:

#include #include #include #ifndef BINSTREE #define BINSTREE 

DO NOT USE ANY OF THAT.

You are only allowed to use:

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

--> NOTE: //part 1 is already working

NOTE: YOU ARE Creating the following methods:

*part 2: implement removal of smallest or largest items extractMin() extractMax()

*part 3: implement a method that finds and removes a given value. remove();

2. Run the program and show a screenshot showing that it works.

//----------------main.cpp-----------

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

int main() { binarySearchTree tree;

tree.insert(15); tree.insert(24); tree.insert(53); tree.insert(-3); tree.insert(23); tree.insert(77); tree.insert(100); tree.insert(17); tree.insert(33); tree.insert(5); tree.insert(-10); tree.insert(2);

tree.display();

//part 1: warmup with some basic methods cout << "number of items: " << tree.numItems() << endl; cout << "number of leaves: " << tree.numLeaves() << endl; cout << "height: " << tree.getHeight() << endl;

//part 2: implement removal of smallest or largest items cout << tree.extractMin() << endl; //displays -10 cout << tree.extractMin() << endl; //displays -3 cout << tree.extractMax() << endl; //displays 100 cout << tree.extractMax() << endl; //displays 77

tree.display(); //verify above 4 values have been removed

// //part 3: implement a method that finds and removes a given value. tree.remove(33); tree.remove(15); tree.remove(5);

tree.insert(43);

tree.display(); //verify above 3 have been removed and insert still works.

return 0; }

// ---------END main.cpp------------------------------------

//-------------binarySearchTree.h--------------------------- #include using namespace std;

class binarySearchTree { private: class node { public: double data; node * left; node * right;

node(double x) { data = x; left = NULL; right = NULL; } };

//root of the tree node * root; //private helper methods //insert x into tree rooted at p void insert(node * &p, double x) { if( p == NULL ) { p = new node(x); } else { if( x > p->data ) { insert(p->right, x); } else { insert(p->left, x); } } }

//--------------------------------------------- int helpNumItems(node * p) { if(p == NULL) { return 0; } else { return 1 + helpNumItems(p->left) + helpNumItems(p->right); } } ////

//----------NumLeaves-------------------- // numLeaves helper Method

int helpNumLeaves(node * p) { if(p == NULL) { return 0; } else if(p->left == NULL && p->right == NULL) { return 1; } else { return helpNumLeaves(p->left) + helpNumLeaves(p->right); } } //--------------------------------------------- //----getHeight Helper Method ----------------- int helpGetHeight(node * p) { if(p == NULL) { return -1; } else { int x = 1 + helpGetHeight(p->right); int y = 1 + helpGetHeight(p->left); if(x { return y; } else { return x; } } }

//helpDisplay method------------- void helpDisplay(node * p) { // node * p = root; if ( p == NULL) { // nothing } else { helpDisplay(p->left); cout << p->data << endl; helpDisplay (p->right); } } //--------------------------------------------- int helpExtractMin(node * p, int x) { if(p == NULL) { return 0; } else { int x = helpExtractMin(p->left, p->data); int y = helpExtractMin(p->right, p->data); int min = p->data; if(x < min) { min = x; } if (p->left == NULL && p->right == NULL) { delete p; } return min; } } //---------------------------------------------

int helpExtractMax(node * p, int x) { if(p == NULL) { return x; } else { int x = helpExtractMax(p->left, p->data); int y = helpExtractMax(p->right, p->data); int max = p->data; if(y > max) { max = y; } // if (p->left == NULL && p->right == NULL) // { // delete p; // } return max; } }

public:

binarySearchTree() { root = NULL; }

~binarySearchTree() { //to be written }

//A wrapper void insert(double x) { insert(root, x); } void display() { helpDisplay(root); } //----------NumLeaves-------------------- int numLeaves() { helpNumLeaves(root); }

//------------- numItems ------------- int numItems () { helpNumItems(root); } //----------------------------- int getHeight() { helpGetHeight(root); } //-----------------------------

int extractMin() { helpExtractMin(root, root->data); } //----------------------------- int extractMax () { helpExtractMax(root, root->data); } };