Q) Add a to_string method to the class BinarySearchTree. This method will return a string representation of the values in the data structure, which will consist of all the values concatenated and separated by ", ". Test your method in main() declaring an object bst:

BinarySearchTree bst; //fill bst with 10 random integers cout << bst.to_string() << endl; 

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

};