Please use C++ to code.

1. Create a Binary Search Tree class with the following methods. This class should contain a node that is defined separately to hold a string.

a. Constructor

b. Destructor

c. Insert accepts a node that is created outside this class. This will find the correct place to insert the node and insert it.

d. Find accepts a value, locates the value in the tree and returns a pointer to the node. If the value isnt in the tree, it will return a null pointer.

e. Size returns the number of elements in the tree as an integer.

f. GetAllAscending returns an array with each node stored in order from smallest to largest (based on the sorting value, not the other data in the node).

g. GetAllDescending returns an array with each node stored in order from largest to smallest (based on the sorting value, not the other data in the node).

h. EmptyTree removes all nodes in the tree in a way to avoid memory leaks.

i. Remove accepts a value, finds the value and removes it from the tree. A pointer to the removed node is returned. The returned node has all pointers set to nullptr. Additionally, if the deleted node has a precedessor, set the predecessor to point left child if present, otherwise right child. In the case of both a left and right child, have the replacement node be the left child, and then have the right child be child of the left . In short make the tree still legal If the value cant be found, it will return a null pointer.

2. Write the code in your main to test the above functions. Include in your lab report what the tree looks like (you can draw it by hand) after inserting the following nodes in the following orders as well as screen shots of the results from calling GetAllAscending and GetAllDescending:

a. Star Wars, Star Trek, Space Balls, Galaxy Quest

b. Cars, Monsters , Inc, The Incredibles, Wall-E

c. Halloween, A Nightmare On Elm Street, Hocus Pocus, Beetlejuice

Discuss why your tree has the structure it has and what can be done to give it a better structure.