Complete the class template of BST to get the yays in main method. Please adhere to the comments. class LookUpBST { //------------------------------------------------------------- // DO NOT

Complete the class template of BST to get the yays in main method. Please adhere to the comments. class LookUpBST, V> { //------------------------------------------------------------- // DO NOT EDIT ANYTHING FOR THIS SECTION EXCEPT TO ADD JAVADOCS //------------------------------------------------------------- //bad practice to have public inst. variables, but we want to test this... //Root of tree public Node root; // size of the tree (the number of nodes) public int size; public int size() { return size; } //provided binary tree node class //bad practice to have public inst. variables, //in a public nested class, but we want to test this... public static class Node { K key; // sorted by key V val; // associated data Node left, right; // left and right subtrees public Node(K key, V val) { this.key = key; this.val = val; } public Node(K key, V val, Node l, Node r) { this.key = key; this.val = val; this.left = l; this.right = r; } } //------------------------------------------------------------- // END OF PROVIDED "DO NOT EDIT" SECTION //------------------------------------------------------------- //------------------------------------------------------------- // You can NOT add any instance/static variables in this class. // You can add methods if needed but they must be PRIVATE. //------------------------------------------------------------- public boolean contains(K key) { // Return true if key is in tree; // return false if key is not in tree or if key is null. // O(H): H as the tree height return false; } public V get(K key) { // Return the value associated with the given key if the key is in tree // Return null if the key is not in tree // throw IllegalArgumentException if key is null // O(H): H as the tree height return null; } public boolean put(K key, V val) { // Insert key, val into tree. // If key is in tree, replace already existing value for this key with the given parameter val // Return false if key, val cannot be added // (null keys). // Return true for a successful insertion. // O(H): H as the tree height return false; } public static  K findBiggestKey(Node t) { // Return the biggest key in the tree rooted at t. // Return null if tree is null. // O(H): H as the tree height return null; } public int height() { // Return the height of the tree. // Return -1 for null trees. // O(N): N is the tree size return 0; } public int numLeaves() { // Return the number of leaf nodes in the tree. // Return zero for null trees. // O(N): N is the tree size return 0; } public String toString() { // Returns a string representation of the tree // Change the function call below to // toStringInOrder: to see (IN-ORDER) string representation of LookUpBST while in debug mode // toStringLevelOrder: to see (LEVEL-ORDER) string representation of LookUpBST in level-order traversal while in debug mode return toStringInOrder(this.root); } private String toStringInOrder(Node t){ // Follow IN-ORDER traversal to include data of all nodes. // Example 1: a single-node tree with the root data as "a:112": // toString() should return a:112 // // Example 2: a tree with four nodes: // d:310 // / \ // a:112 p:367 // / // f:330 // toStringInOrder() should return a:112 d:310 f: 330 p:367 if (t==null) return ""; StringBuilder sb = new StringBuilder(); sb.append(toStringInOrder(t.left)); sb.append(t.key); sb.append(":"); sb.append(t.val); sb.append(" "); sb.append(toStringInOrder(t.right)); return sb.toString(); } private String toStringLevelOrder(Node t) { // Follow LEVEL-ORDER traversal to include data of all nodes. // Example: a tree with four nodes: // d:310 // / \ // a:112 p:367 // / // f:330 // toStringLevel() should return // d:310 // a:112 p:367 // null null f:330 null StringBuilder sb = new StringBuilder(); int capacity = (int)Math.pow(2,size()+1)-1; Node[] list = new Node[capacity]; list[0] = root; int count = 0; int level = 0; for(int i = 0; i < capacity; i++) { if(i == Math.pow(2,level+1)-1) { if(count == size) break; level++; sb.append(" "); } if(list[i] == null) { sb.append("null "); } else { count++; sb.append(list[i].key); sb.append(":"); sb.append(list[i].val); sb.append(" "); if((i*2)+1 < list.length) { list[(i*2)+1] = list[i].left; list[(i*2)+2] = list[i].right; } } } return sb.toString(); } //------------------------------------------------------------- // Main Method For Your Testing -- Edit all you want //------------------------------------------------------------- public static void main(String[] args) { LookUpBST t = new LookUpBST(); //build the tree / set the size manually //only for testing purpose Node node = new Node<>("a", 112); Node node2 = new Node<>("f", 330); node2 = new Node<>("p", 367, node2,null); node = new Node<>("d", 310,node,node2); t.root = node; t.size = 4; // Current tree: // d:310 // / \ // a:112 p:367 // / // f:330 //System.out.println(t.toString()); //checking basic features if (t.root.key == "d" && t.contains("f") && !t.contains("z") && t.height() == 2){ System.out.println("Yay 1"); } //checking more features if (t.numLeaves() == 2 && LookUpBST.findBiggestKey(t.root)=="p"){ System.out.println("Yay 2"); } t = new LookUpBST(); if (t.put("d", 310) && !t.put(null, null) && t.size()==1 && t.height()==0 && t.put("a", 112) && t.put("p", 367) && t.put("f", 330) && t.get("p") == 367){ System.out.println("Yay 3"); } if (t.size()==4 && t.height()==2 && t.root.key == "d" && t.root.left.key == "a" && t.root.right.key== "p" && t.root.right.left.key == "f"){ System.out.println("Yay 4"); } // more insertion t.put("s", 465); t.put("e", 321); t.put("b", 211); // d:310 // / \ // a:112 p:367 // \ / \ // b:211 f:330 s:465 // / // e:321 if (t.size()==7 && t.height() == 3 && LookUpBST.findBiggestKey(t.root.left) == "b"){ System.out.println("Yay 5"); } // Uncomment the following lines to see an IN-ORDER and a LEVEL-ORDER string representation of the tree, in that order. //System.out.println(t.toStringInOrder(t.root)); //System.out.println(t.toStringLevelOrder(t.root)); } }