C++ Recursion Assigment.

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

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); } };