Binary Search Tree Solution




This project will give you experience with Binary Search Trees. You will build upon this project with the next project, so be sure you document your code well and understand well how it works.

Implement the two classes defined in the following UM L diagrams.

-+ root: Node-






-•BinaryS •• rcnrr •• O

+Insert(data:ilt): void

•lnsertHefpet(cursor.Node’, data:int): Node’

+Search(data:int): Nodes

•SearehHelper(eursor:Node’, data:lnl~ Node’

+Remove(dala:int): void

•RemoveHelper(eursor.NOde’, data.inl). NOde’

+lnorderTraversal(): void

•lnorderHelper(eursor:NOde’): void

-Pnntt): void

•PrlntHelper(O”Setstd::string&’, cursor.NOde’): voto

-Size(): int

•SlzeHelper(cursor.Node’): inl

+leftChilct Node”

-righIChHd: Node’

•neededForunuest Observer

-Node(data:inl, lenChil<l:Node’, rightChild:NOde’)

.. NOd.O

-ISleatO : boot

-UpdateHeightO : void

You need to implement these two UML diagrams in:

Node.h Node.cpp BinarySearchTree.h BinarySearchTree.cpp


The following functions in BinarySearchTree MUST be implemented using recursion (their recursive ‘helper” functions are specified in the

UML diagram):

Insert Search Remove




Unit Testing

ZyLabs will be auto-grading this project

The Node and BinarySearchTree classes must be implemented EXACTLYas shown in the above UML diagrams. Main.cpp MUST include “Ooserver.h’ and ‘RecursionCounter.h’ near the beginning of the file.

Main.cpp MUST define the following four static variables for these two classes as shown below:

include”BinarySearchTree.h” include”Observer.h” include”RecursionCounter.h”

II needed for Unit Testing. DO NOT REMOVE intObserver::numConstructions = 0; intObserver::numDestructions = 0; intRecursionCounter::currentDepth = 0; intRecursionCounter::maxDepth = 0;

int mainO


Also, to assist the Unit Testing portion of ZyLabs, the Node class MUST have a private variable of type “Observer’. This means that Node.h must #include “Observer.h’ at the top of the file. i.e.:





1/ your code goes here


Observer neededForUnitTest; /1 do not remove


To allow the Unit Test to verify that recursion is properly being used, one local variable of type RecursionCounter needs to be declared at the beginning of EACH** Recursive ‘Helper” function**. For example:

intBinarySearchTree::SizeHelper(Node * cursor)


RecursionCounter neededForUnitTest; /1 MUST BE HERE

1/ base case

Main Driver

In Main.cpp implement the function mainO which creates a BinarySearchTree object and performs the following:

1. Insert the following data into your tree:

2. 21,26,30,9,4,14,28,18,1 5,10,2,3,7

3. Perform an In-order traversal of the tree

4. Print the tree

5. Remove the following data from the tree

6. 21,9,4,18,15,7

7. Print the tree

8. Perform an In-order traversal of the tree

The output should look like:

Image missing