For this assignment you are required to develop a Binary Search Tree Data Structure.

Your program will have $3$ classes.

Node $($Reusable Data Independent Class$)$

a$.$ This class should be a template

b$.$ Private variables are:

i$.T^{***}$ data

ii$.$ Node $**$ leftChild

iii. Node ${?}^{***}$ rightChild

iv$.$ Node ${?}^{***}$ parent

c$.$ This class must have a constructor, it can be overloaded if you choose to

d$.$ This class must have a print method.

e$.$ Since all variables are private, to access them, you must write set & get methods for each variable:

i$.$ Set methods have one argument and perform assignment to the variable

ii$.$ Get method returns the value of the variable to the method calling it$.$ Set the appropriate return type.

Binary Search Tree $($Reusable Data Independent Class$)$

a$.$ This class should be a template

b$.$ Private variables are:

i$.$ Node ${?}^{**}$ root

ii$.$ int numberOfElements

iii. int height

c$.$ Since all variables are private, to access them, you must write set & get methods for each variable:

i$.$ Set methods have one argument and perform assignment to the variable

ii$.$ Get method returns the value of the variable to the method calling it$.$ Set the appropriate return type.

$1$

d$.$ This class must have a constructor, it can be overloaded if you choose to

e$.$ This class must have a destructor that is explicitly written.

f$.$ This class must have a print method $-$ The print method must traverse the tree in "PRE ORDER" and print the elements that way. The actual data being printed however, cascades upwards and you cannot make it data class dependent.

g$.$ This class must also contain the following methods:

i$.$ findKthElement$($int $k)-$ this method finds the element in the kth in ascending order of elements in the tree and prints it$.$ It returns nothing.

Consider edge cases and account for them.

ii$.$ findSmallestElement$()-$ this method finds the smallest element in the tree and prints it$.$ It returns nothing.

iii. findBiggestElement$()-$ this method finds the biggest element in the tree and prints it$.$ It returns nothing.

iv$.$ sortAscending$()-$ this method prints all the elements stored in the BST in ascending order. It returns nothing.

This method must be written recursively, not iteratively.

This method returns nothing.

v$.$ sortDescending$()-$ this method prints all the elements stored in the BST in descending order.

This method must be written recursively, not iteratively.

This method returns nothing.

$3.$ Data

a$.$ Private Variable:

i$.$ int value

b$.$ Since all variables are private, to access them, you must write set & get methods for each variable:

i$.$ Set methods have one argument and perform assignment to the variable

ii$.$ Get method returns the value of the variable to the method calling it$.$ Set the appropriate return type.

c$.$ This class must have a constructor, it can be overloaded if you choose to

d$.$ This class must have a print method.

$2$

Main method:

This is the main$()$ that you are required to use in your program.

You may not make any changes to the main method.

Please note this method may require you to name your classes and methods a certain way, do so accordingly. Expected output is more than what is shown