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.