Requirements: 1) Create a templated Binary Search Tree class with the following methods

Requirements:

1) Create a templated Binary Search Tree class with the following methods. You may need or find it easier to create private methods and variable to simplify or eliminate duplicate code in the methods below such as RotateRight, RotateLeft or NodeHeight. a. Constructor b. Destructor C. Insert - accepts a value, creates a node and inserts the node into the tree in the appropriate location. This should rebalance the tree as necessary so the tree remains balanced at all times. If the value already exists in the tree, this should throw an error. d. Find - accepts a value, locates the value in the tree and returns a pointer to the node. If the value isn't 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. This should rebalance the tree as necessary so the tree remains balanced at all times.