Add a recursive function getHeight to the BinarySearchTree class in Exercise 1 that returns the height of the tree.

Exercise 1

main.cpp

#include "stdafx.h" #include "BinarySearchTree.h" #include "time.h" #include

using namespace std;

int main() { BinarySearchTree bst;

int x;

if (bst.isEmpty()) cout << "BST is empty" << endl; else cout << "BST is not empty" << endl;

srand((unsigned int)time(0));

for (int i = 0; i < 10; i++) bst.add(rand() % 20);

if (bst.isEmpty()) cout << "BST is empty" << endl; else cout << "BST is not empty" << endl;

bst.display();

x = rand() % 20;

if (bst.search(x)) cout << x << " was found!" << endl; else cout << x << " was not found!" << endl;

cout << "Minimum of the tree = " << bst.getMinimum() << endl;

return 0; }

BinarySearchTree.h

#pragma once struct TreeNode { int info; //element stored in this node TreeNode *left; //link to left child TreeNode *right; //link to right child };

class BinarySearchTree { public: BinarySearchTree(); bool isEmpty(); void display(); bool search(int); void add(int); int getMinimum(); ~BinarySearchTree();

private: TreeNode* root;

void inorderDisplay(TreeNode*); bool search(int, TreeNode*); void add(int, TreeNode* &); TreeNode* getMinimum(TreeNode*); void deallocateMemory(TreeNode* &); };

BinarySearchTree.cpp

#include "stdafx.h" #include "BinarySearchTree.h" #include using namespace std;

BinarySearchTree::BinarySearchTree() { root = NULL; }

bool BinarySearchTree::isEmpty() { return root == NULL; }

void BinarySearchTree::display() { inorderDisplay(root); cout << endl; }

bool BinarySearchTree::search(int x) { return search(x, root); }

void BinarySearchTree::add(int x) { add(x, root); }

int BinarySearchTree::getMinimum() { return getMinimum(root)->info; }

BinarySearchTree::~BinarySearchTree() { deallocateMemory(root); }

void BinarySearchTree::inorderDisplay(TreeNode *p) { if (p != NULL) { inorderDisplay(p->left); cout << p->info << " "; inorderDisplay(p->right); } }

void BinarySearchTree::add(int x, TreeNode* & p) { if (p == NULL) { p = new TreeNode; p->info = x; p->left = p->right = NULL; } else { if (x <= p->info) add(x, p->left); else add(x, p->right); } }

bool BinarySearchTree::search(int x, TreeNode* p) { if (p == NULL) return false; else if (x == p->info) return true; else if (x < p->info) return search(x, p->left); else return search(x, p->right); }

TreeNode* BinarySearchTree::getMinimum(TreeNode* p) { if (p->left == NULL) return p; else return getMinimum(p->left); }

void BinarySearchTree::deallocateMemory(TreeNode* & p) { if (p != NULL) { deallocateMemory(p->left); deallocateMemory(p->right); delete p;

p = NULL; } }