Fix the code so it pass the tests.

(Header.h)

#ifndef BINARY_TREE_H #define BINARY_TREE_H #include #include #include #include #include

using namespace std;

template struct Node { Type item; Node* left; Node* right; };

template class BinaryTree { public: BinaryTree(); ~BinaryTree(); void insert(Type item); void preOrder(); void inOrder(); void postOrder(); int nodeCount(); Node* find(Type item); Node* findRightMostNode(Node* find); void remove(Type item); int height(); int leavesCount();

protected: Node* root;

private: void destroy(Node*); void insert(Type item, Node*); void preOrder(Node*); void postOrder(Node*); void inOrder(Node*); int nodeCount(Node*); int leavesCount(Node*); Node* find(Type item, Node*); Node* remove(Type item, Node*);

int height(int level, Node*); void deleteFromTree(Node*& p); };

template BinaryTree::BinaryTree() { root = nullptr; }

template BinaryTree::~BinaryTree() { destroy(root); }

template void BinaryTree::destroy(Node* curr) { if (curr != nullptr)

{

destroy(curr->left);

destroy(curr->right);

delete curr;

curr = nullptr; } }

template void BinaryTree::insert(Type item) {

insert(item, root);

}

template void BinaryTree::insert(Type item, Node* curr) {

Node* current; // pointer to traverse the tree

Node* trailCurrent = nullptr; // pointer behind current

Node* newNode; // pointer to create the node

newNode = new Node;

assert(newNode != nullptr);

newNode->item = item;

newNode->left = nullptr;

newNode->right = nullptr;

if (root == nullptr)

{

root = newNode;

} else

{

current = curr;

while (current != nullptr)

{

trailCurrent = current;

if (current->item == item)

{

cerr << "The insert item is already in the list-";

cerr << "duplicates are not allowed." << endl;

return; }

else if (current->item > item)

current = current->left;

else

current = current->right;

} // end while

if (trailCurrent->item > item)

trailCurrent->left = newNode;

else

trailCurrent->right = newNode; }

}

template void BinaryTree::preOrder() { preOrder(root); } template void BinaryTree::preOrder(Node* p) {

if (p != nullptr)

{

cout << p->item << " ";

preorder(p->left);

preorder(p->right); } }

template void BinaryTree::inOrder() { inOrder(root); }

template void BinaryTree::inOrder(Node* p) { if (p != nullptr)

{

inOrder(p->left);

cout << p->item << " ";

inOrder(p->right); } }

template void BinaryTree::postOrder() { postOrder(root); } template void BinaryTree::postOrder(Node* p) { if (p != nullptr)

{

cout << p->item << " ";

postOrder(p->left);

postOrder(p->right); } }

template int BinaryTree::nodeCount() { nodeCount(root); }

template int BinaryTree::nodeCount(Node* root) { if (root == NULL) return 0;

// recursive call to left child and right child and // add the result of these with 1 ( 1 for counting the root) return 1 + countNode(root->left) + countNode(root->right); }

template int BinaryTree::leavesCount() { return leavesCount(root); }

template int BinaryTree::leavesCount(Node* curr) {

if (curr == nullptr) return 0; if (curr->left == nullptr && curr->right == nullptr) return 1; else return leavesCount(curr->left) + leavesCount(curr->right); }

template Node* BinaryTree::find(Type item) { return find(item, root); }

template Node* BinaryTree::find(Type searchItem, Node* root) { Node* current;

bool found = false;

if (root == nullptr)

return nullptr;

else

{

current = root;

while (current != nullptr && !found)

{

if (current->item == searchItem) { return current; }

else if (current->item > searchItem)

current = current->left;

else

current = current->right;

} // end while

} // end else

return nullptr; }

template Node* BinaryTree::findRightMostNode(Node* root) {

if (root == nullptr) { return nullptr; } if (root->right == nullptr) { return root; } return findRightMostNode(root->right);

}

template void BinaryTree::deleteFromTree(Node*& p)

{

Node* current; // pointer to traverse the tree

Node* trailCurrent; // pointer behind current

Node* temp; // pointer to delete the node

if (p == nullptr)

cerr << "Error: The node to be deleted is nullptr." << endl;

else if (p->left == nullptr && p->right == nullptr)

{

temp = p;

p = nullptr;

delete temp; }

else if (p->left == nullptr)

{

temp = p;

p = temp->right;

delete temp; }

else if (p->right == nullptr)

{

temp = p;

p = temp->left;

delete temp; }

else

{

current = p->left;

trailCurrent = nullptr;

while (current->right != nullptr)

{

trailCurrent = current;

current = current->right;

} // end while

p->item = current->item;

if (trailCurrent == nullptr) // current did not move; current == p->left; adjust p

p->left = current->left;

else

trailCurrent->right = current->left;

delete current;

} // end else

} // end deleteFromTree

template void BinaryTree::remove(Type item) { remove(item, root); }

template Node* BinaryTree::remove(Type deleteItem, Node* curr) { Node* current; // pointer to traverse the tree

Node* trailCurrent; // pointer behind current

bool found = false;

if (root == nullptr)

cout << "Cannot delete from the empty tree." << endl;

else

{

current = root;

trailCurrent = root;

while (current != nullptr && !found)

{

if (current->item == deleteItem)

found = true;

else

{

trailCurrent = current;

if (current->item > deleteItem)

current = current->left;

else

current = current->right; }

} // end while

if (current == nullptr)

cout << "The delete item is not in the tree." << endl;

else if (found)

{

if (current == root)

deleteFromTree(root);

else if (trailCurrent->item > deleteItem)

deleteFromTree(trailCurrent->left);

else

deleteFromTree(trailCurrent->right);

} // end if } return root; }

template int BinaryTree::height() { return height(0, root); } template int BinaryTree::height(int level, Node* node) { if (node == nullptr) return -1; else { /* compute the depth of each subtree */ int lDepth = height(0, node->left); int rDepth = height(0, node->right);

/* use the larger one */ if (lDepth > rDepth) return(lDepth + 1); else return(rDepth + 1); } }

#endif // BINARY_TREE_H

(Tester.cpp)

#include #include #include #include "BinaryTree.h"

using namespace std; bool checkTest(string testName, bool condition); bool checkTest(string testName, int whatItShouldBe, int whatItIs); void testFindMethod(); void testRightMostNodeSearch(); void deleteTest(); void testHeight(); void testLeavesCount();

BinaryTree populateTree();

int main() { BinaryTree myTree = populateTree(); myTree.inOrder(); cout << endl; testFindMethod(); testRightMostNodeSearch(); deleteTest(); testHeight(); testLeavesCount(); cout << "Completed the Program" << endl; return 0; }

BinaryTree populateTree(){ BinaryTree myTree; int values[] = {37, 32, 73, 95, 42, 12, 0, 49, 98, 7, 27, 17, 47, 87, 77, 97, 67, 85, 15, 5, 35, 55, 65, 75, 25, 45, 3, 93, 83, 53, 63, 23, 13, 43, 33}; int size = (sizeof(values)/sizeof(*values));

for(int i = 0; i < size; i++){ myTree.insert(values[i]); }

return myTree; }

void testFindMethod( ){ BinaryTree myTree = populateTree(); auto ptr = myTree.find(49); checkTest("Test 1: Find(49)", 49, ptr->item); ptr = myTree.find(200); checkTest("Test 2: Find(200)", ptr == nullptr); }

void testRightMostNodeSearch(){ BinaryTree myTree = populateTree(); auto ptr = myTree.find(49); auto ptrchild = myTree.findRightMostNode(ptr);

checkTest("Test 3: RightNodeTest(49)", 67, ptrchild->item); }

void deleteTest(){ BinaryTree myTree = populateTree(); myTree.remove(33); auto ptr = myTree.find(33); if(!checkTest("Test 4: Delete Leaf: 33", ptr == nullptr)){ cout << "In Order: "; myTree.inOrder(); cout << endl; }

myTree.remove(67); ptr = myTree.find(67); if(!checkTest("Test 5: Delete Node with Left Child: 67", ptr == nullptr)){ cout << "In Order: "; myTree.inOrder(); cout << endl; }

myTree.remove(42); ptr = myTree.find(42); if(!checkTest("Test 6: Delete Node with Right Child: 42", ptr == nullptr)){ cout << "In Order: "; myTree.inOrder(); cout << endl; }

myTree.remove(73); ptr = myTree.find(73); if(!checkTest("Test 7: Delete Node with two children: 73", ptr == nullptr)){ cout << "In Order: "; myTree.inOrder(); cout << endl; }

myTree.remove(37); ptr = myTree.find(37); if(!checkTest("Test 8: Delete root: 37", ptr == nullptr)){ cout << "In Order: "; myTree.inOrder(); cout << endl; } }

void testHeight(){ BinaryTree myTree = populateTree(); checkTest("Test 9: height()", 7 == myTree.height()); }

void testLeavesCount(){ BinaryTree myTree = populateTree(); checkTest("Test 10: leavesCount()", 11 == myTree.leavesCount()); }

//Helps with Testing bool checkTest(string testName, int whatItShouldBe, int whatItIs) {

if (whatItShouldBe == whatItIs) { cout << "Passed " << testName << endl; return true; } else { cout << "***Failed test " << testName << " *** " << endl << " Output was " << whatItIs << endl << " Output should have been " << whatItShouldBe << endl; return false; } } //Helps with Testing bool checkTest(string testName, bool condition) {

if (condition) { cout << "Passed " << testName << endl; return true; } else { cout << "***Failed test " << testName << " *** " << endl; return false; }

}