Question: Provide an appropriate data structure and necessary methods to build a binary search tree which enables you to complete the rest of this assignment. Define your class with the generic types.

This is a practice on design, implement and analyzing problems using binary search trees. The main function of your test program (testBST.cpp) should be compatible with the following main function. By compatible it means the number of parameters of each function should match. The type of parameters is determined by your design and implementation. This makes some constraints in your design, which is likely to occur in the real world.

int main() { // declaration of your variables ... n1 = getInput(); // either generates a random non-negative // integer or reads it from input list1 = genData(n1); //generates a list of n1 random numbers [-n1, n1] cout << "The List1: "; printList(list1); //prints elements of the given list n2 = getInput(); list2 = genData(n2); //generates a list of n2 random numbers [-n2, n2] printList(list2); bst1 = makeBST(list1); cout << "In-order traversal of bst1 is: "; printBT(bst1); remove(list1[n1/2], bst1); // removes list1[n1/2] from corresponding tree (bst1)

cout << "In-order traversal of bst1 after deleting " <