Q) Add a recursive function getHeight to the BinarySearchTree class in the Code(Proect below) that returns the height of the tree. Test your function.

Below is the code for (BinarySearchTree.cpp, main.cpp , BinarySearchTree.h)

BinarySearchTree.cpp

/********************************************

* Week 6 lesson: *

* implementation of a binary search tree *

*********************************************/

#include

#include "BinarySearchTree.h"

using namespace std;

//Public functions

/*

* Initializes the bst to empty.

*/

BinarySearchTree::BinarySearchTree()

{

root = NULL;

}

/*

* Determines whether the bst is empty

*

* Returns true if the bst is empty, false otherwise

*/

bool BinarySearchTree::isEmpty()

{

return root == NULL;

}

/*

* Prints the bst elements using inorder traversal. This method invokes the

* private method inorderDisplay, passing to it the root of the actual tree.

*/

void BinarySearchTree::display()

{

inorderDisplay(root);

cout << endl;

}

/*

* Determines if an item exists in the bst. This method invokes the private

* method search, passing to it the element to be found and the root

* of the actual tree.

*

* x: element to be found.

*

* Returns true if x is found in the bst, false otherwise.

*/

bool BinarySearchTree::search(int x)

{

return search(x, root);

}

/*

* Adds the element x to the bst. This method invokes the private method

* add, passing to it the element to be added to the bst and the root

* of the actual tree.

*

* x: element to be added to the bst.

*/

void BinarySearchTree::add(int x)

{

add(x, root);

}

/*

* Finds the smallest value in the bst. This method invokes the overloaded

* method getMinimum, passing to it the root of the tree.

*

* Returns the smallest value in the bst.

*/

int BinarySearchTree::getMinimum()

{

return getMinimum(root)->info;

}

/*

* Destructor. Invokes the method deallocateMemory, passing to it the root

* of the tree.

*/

BinarySearchTree::~BinarySearchTree()

{

deallocateMemory(root);

}

//Private functions

/*

* Prints the elements of the subtree whose root is pointed to by p. Uses

* inorder traversal.

*

* p: root of subtree.

*/

void BinarySearchTree::inorderDisplay(TreeNode *p)

{

if (p != NULL)

{

inorderDisplay(p->left);

cout << p->info << " ";

inorderDisplay(p->right);

}

}

/*

* Adds x to the subtree pointed to by p. The search for the location to

* insert the new node is conducted recursively, using the bst property:

* keys in the left subtree of a node are smaller than or equal to the key

* in the node, while the keys in the right subtree of the node are greater.

*

* x: element to be added to the subtree.

* p: root of subtree.

*/

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

}

}

/*

* Finds if x is present in the subtree whose root is pointed to by p. The

* search is conducted recursively, using the bst property: keys in the left

* subtree of a node are smaller than or equal to the key in the node, while

* the keys in the right subtree of the node are greater.

*

* x: element to be found.

* p: root of subtree.

*

* Returns true if x is found in this subtree, false otherwise.

*/

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

}

/*

* Recursively finds the smallest value in the subtree pointed to by p.

* The method uses this property of BSTs: the smallest value is stored in

* the leftmost node.

*

* p: root of subtree.

*

* Returns smallest value in the subtree pointed to by p.

*/

TreeNode* BinarySearchTree::getMinimum(TreeNode* p)

{

if (p->left == NULL) return p;

else return getMinimum(p->left);

}

/*

* Recursively deallocates the memory of the subtree pointed to by p.

*

* p: root of subtree.

*/

void BinarySearchTree::deallocateMemory(TreeNode* & p)

{

if (p != NULL)

{

deallocateMemory(p->left);

deallocateMemory(p->right);

delete p;

p = NULL;

}

}

main.cpp

/********************************************

* Week 6 lesson: *

* implementation of a binary search tree *

*********************************************/

#include

#include "BinarySearchTree.h"

#include "time.h"

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

/********************************************

* Week 6 lesson: *

* implementation of a binary search tree *

*********************************************/

/*

* Binary search tree node.

*/

struct TreeNode

{

int info; //element stored in this node

TreeNode *left; //link to left child

TreeNode *right; //link to right child

};

/*

* Class implementing a binary search tree.

*/

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* &);

};