Write your own class that implements a binary search tree. Use the following UML diagram and attribute descriptions. Place all the code for the class in a single header file named Tree.h. Be sure to include preprocessor guards.

Note -- clear(r : Node*&) : void should be private

Class Attributes:

Node - a private, nested struct.

i - an int that stores the value in the tree.

left - a Node pointer that stores the memory address of the left child.

right - a Node pointer that stores the memory address of the right child.

root - a Node pointer that stores the memory address of the root node.

constructor - initializes root to null.

destructor - frees all memory used by the Tree.

add - a public method that calls the private add method, passing it the root pointer and it's argument.

add - a private method that is called by public add. Accepts the root pointer by reference and and integer to add to the tree as it's only arguments.

remove - a public method that calls the private remove method, passing it the root pointer and it's argument.

remove - a private method that is called by the public remove method. Accepts the root pointer, by reference, and a value to search for and remove from the tree as it's only arguments.

find - a public method that calls the private find method, passing it's argument and the root pointer to the private find method. Returns the value returned by the private find method.

find - a private method that accepts a root pointer and value to search for in the tree. Returns true if it's found, false otherwise.

print - a public method that calls the private print method, passing the root pointer to the private print method.

print - a private method that accepts the root pointer as it's only argument. Prints the contents of the tree using in-order traversal.

clear - a public method that calls the private clear method, passing the root pointer to the private clear method.

clear - a private method that accepts the root pointer by reference. Frees all memory used by the tree.

Notes:

Accessors should be marked const.

The only method that interacts with the user is public print. It has a cout statement, but no cin statements. No other method contains cin or cout statements.

You are not writing an entire program, just a class.

After calling clear, root should be set back to null.

Hints:

If your program crashes, you're almost certainly accessing an invalid memory location or suffering from infinite recursion.

Make sure you pay attention to passing by reference when it's needed.

Tree Node i: int left: Node* ight: Node -root: Node* +Tree() +-Tree() +add(i: int): void -add(r Node*&, i : int): void tremove(i : int) void -remove(r Node*&, i : int): void +find(i : int) bool find(r Node*, i: int):bool +print() : void print(r Node*): void +clear(): void +clear(r Node*&) :void