public class GenericBST { private Node root; private static class Node { final Integer key; final V value; Node left, right, parent; Node(Integer key, V value) { this.key = key; this.value = value; } public String toString() { StringBuilder str = new StringBuilder(); str.append("(" + key + "," + value + ") "); return str.toString(); } } GenericBST() { root = null; } public void add(Integer k, V val) { Node newestNode = new Node(k,val); if(root == null) { root = newestNode; return; } //... } public V remove(Integer k) { V valToReturn = null; //... return valToReturn; } public V valueForTheKthSmallestKey(Integer k) { V valToReturn = null; //... return valToReturn; } public String toString() { //... } }

1 Description Implement a generic binary search tree class GenericBST with the following methods. The constructor must be a no argument constructor. Each node in the tree must contain a key (always an Integer) and the corresponding value of type V. For example, if we want values to be of type String, then we use the following statement to create the binary search tree. GenericBST myBST - new GenericBSTO; 1. public void add(Integer k, V val); is method adds a pair to the tree by creating a new node and inserting it at the appro- priate position. 2. public V remove(Integer k); This method removes a node from the tree which has the key k. If such a node exists, return the value stored in that node else return null. 3. public V valueForTheKthSmallestKey(Integer k); This method returns the value corresponding to the kth smallest key in the tree. If k is greater than the number of nodes in the tree, return null. 4. public String toStringO; This method returns the inorder traversal of the tree. Here is an example. Consider the case when is String and the nodes in the tree are (10, "Alice"), (20, "Bob"), (90, "Pat"), arranged in inorder fashion. Then this method must return the following string (notice the whitespaces in between) (10,Alice) (20,Bob) (90,Pat) Unless stated, in the programs of this course you are not allowed to use any existing Java library and/or external packages for solving the problem. You should write everything from the scratch. You will receive zero if your program does not compile or it is found that you have copied code from some other source without any reference. 2 Deliverable Upload the file GenericBST.java only. You are not allowed to submit any other file. Your java code should be properly indented and nicely commented. Feel free to use additional helper methods, if required. 1 Description Implement a generic binary search tree class GenericBST with the following methods. The constructor must be a no argument constructor. Each node in the tree must contain a key (always an Integer) and the corresponding value of type V. For example, if we want values to be of type String, then we use the following statement to create the binary search tree. GenericBST myBST - new GenericBSTO; 1. public void add(Integer k, V val); is method adds a pair to the tree by creating a new node and inserting it at the appro- priate position. 2. public V remove(Integer k); This method removes a node from the tree which has the key k. If such a node exists, return the value stored in that node else return null. 3. public V valueForTheKthSmallestKey(Integer k); This method returns the value corresponding to the kth smallest key in the tree. If k is greater than the number of nodes in the tree, return null. 4. public String toStringO; This method returns the inorder traversal of the tree. Here is an example. Consider the case when is String and the nodes in the tree are (10, "Alice"), (20, "Bob"), (90, "Pat"), arranged in inorder fashion. Then this method must return the following string (notice the whitespaces in between) (10,Alice) (20,Bob) (90,Pat) Unless stated, in the programs of this course you are not allowed to use any existing Java library and/or external packages for solving the problem. You should write everything from the scratch. You will receive zero if your program does not compile or it is found that you have copied code from some other source without any reference. 2 Deliverable Upload the file GenericBST.java only. You are not allowed to submit any other file. Your java code should be properly indented and nicely commented. Feel free to use additional helper methods, if required