This is the outline for the Generic BST code... just need help filling it in :

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 GenericBST(); 1. public void add (Integer k, V val); This method adds a pair to the tree by creating a new node and inserting it at the appro- priate position. 2. public V removeCInteger ); 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 case when V 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): is an example. Consider the (10,Alice) (20,Bob) (99,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 urite everything from the scratch. You will receive zero ifyour 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