given :

* DO NOT EDIT THIS FILE. public class BSTNode> { private T data; private BSTNode left; private BSTNode right; /** Please complete :

import java.util.Collection; import java.util.List; /**  * Your implementation of a binary search tree.  *  */ public class BST> { // DO NOT ADD OR MODIFY INSTANCE VARIABLES. private BSTNode root; private int size; /**  * A no-argument constructor that should initialize an empty BST.  *  * Since instance variables are initialized to their default values, there  * is no need to do anything for this constructor.  */  public BST() { // DO NOT IMPLEMENT THIS CONSTRUCTOR! } /**  * Initializes the BST with the data in the Collection. The data  * should be added in the same order it is in the Collection.  *  * Hint: Not all Collections are indexable like Lists, so a regular  * for loop will not work here. What other type of loop would work?  *  * @param data the data to add to the tree  * @throws IllegalArgumentException if data or any element in data is null  */  public BST(Collection data) { } /**  * Add the data as a leaf in the BST. Should traverse the tree to find the  * appropriate location. If the data is already in the tree, then nothing  * should be done (the duplicate shouldn't get added, and size should not be  * incremented).  *  * Should have a running time of O(log n) for a balanced tree, and a worst  * case of O(n).  *  * @throws IllegalArgumentException if the data is null  * @param data the data to be added  */  public void add(T data) { } /**  * Removes the data from the tree. There are 3 cases to consider:  *  * 1: the data is a leaf. In this case, simply remove it.  * 2: the data has one child. In this case, simply replace it with its  * child.  * 3: the data has 2 children. Use the successor to replace the data.  * You must use recursion to find and remove the successor (you will likely  * need an additional helper method to handle this case efficiently).  *  * Should have a running time of O(log n) for a balanced tree, and a worst  * case of O(n).  *  * @throws IllegalArgumentException if the data is null  * @throws java.util.NoSuchElementException if the data is not found  * @param data the data to remove from the tree.  * @return the data removed from the tree. Do not return the same data  * that was passed in. Return the data that was stored in the tree.  */  public T remove(T data) { } /**  * Returns the data in the tree matching the parameter passed in (think  * carefully: should you use value equality or reference equality?).  *  * Should have a running time of O(log n) for a balanced tree, and a worst  * case of O(n).  *  * @throws IllegalArgumentException if the data is null  * @throws java.util.NoSuchElementException if the data is not found  * @param data the data to search for in the tree.  * @return the data in the tree equal to the parameter. Do not return the  * same data that was passed in. Return the data that was stored in the  * tree.  */  public T get(T data) { } /**  * Returns whether or not data equivalent to the given parameter is  * contained within the tree. The same type of equality should be used as  * in the get method.  *  * Should have a running time of O(log n) for a balanced tree, and a worst  * case of O(n).  *  * @throws IllegalArgumentException if the data is null  * @param data the data to search for in the tree.  * @return whether or not the parameter is contained within the tree.  */  public boolean contains(T data) { } /**  * Should run in O(n).  *  * @return a preorder traversal of the tree  */  public List preorder() { } /**  * Should run in O(n).  *  * @return an inorder traversal of the tree  */  public List inorder() { } /**  * Should run in O(n).  *  * @return a postorder traversal of the tree  */  public List postorder() { } /**  * Generate a level-order traversal of the tree.  *  * To do this, add the root node to a queue. Then, while the queue isn't  * empty, remove one node, add its data to the list being returned, and add  * its left and right child nodes to the queue. If what you just removed is  * {@code null}, ignore it and continue with the rest of the nodes.  *  * Should run in O(n).  *  * @return a level order traversal of the tree  */  public List levelorder() { } /**  * Finds and retrieves the k-largest elements from the BST in sorted order,  * least to greatest.  *  * In most cases, this method will not need to traverse the entire tree to  * function properly, so you should only traverse the branches of the tree  * necessary to get the data and only do so once. Failure to do so will  * result in the efficiency penalty.  *  * EXAMPLE: Given the BST below composed of Integers:  *  * 50  * / \  * 25 75  * / \  * 12 37  * / \ \  * 10 15 40  * /  * 13  *  * kLargest(5) should return the list [25, 37, 40, 50, 75].  * kLargest(3) should return the list [40, 50, 75].  *  * Should have a running time of O(log(n) + k) for a balanced tree and a  * worst case of O(n + k).  *  * @throws java.lang.IllegalArgumentException if k > n, the number of data  * in the BST  * @param k the number of largest elements to return  * @return sorted list consisting of the k largest elements  */  public List kLargest(int k) { } /**  * Clears the tree.  *  * Should run in O(1).  */  public void clear() { } /**  * Calculate and return the height of the root of the tree. A node's  * height is defined as {@code max(left.height, right.height) + 1}. A leaf  * node has a height of 0 and a null child should be -1.  *  * Should be calculated in O(n).  *  * @return the height of the root of the tree, -1 if the tree is empty  */  public int height() { } /**  * THIS METHOD IS ONLY FOR TESTING PURPOSES.  *  * DO NOT USE THIS METHOD IN YOUR CODE.  *  * @return the number of elements in the tree  */  public int size() { // DO NOT MODIFY THIS METHOD return size; } /**  * THIS METHOD IS ONLY FOR TESTING PURPOSES.  *  * DO NOT USE THIS METHOD IN YOUR CODE.  *  * @return the root of the tree  */  public BSTNode getRoot() { // DO NOT MODIFY THIS METHOD! return root; } } 

 * Create a BST node with the given data.  *  * @param data the data to be stored in this node.  */  public BSTNode(T data) { this.data = data; } /**  * Get the data in this node.  *  * @return data in this node.  */  public T getData() { return data; } /**  * Set the data in this node.  *  * @param data data to be placed into the node.  */  public void setData(T data) { this.data = data; } /**  * Get the node to the left of this node.  *  * @return node to the left.  */  public BSTNode getLeft() { return left; } /**  * Set the node to the left of this node.  *  * @param left new node to the left.  */  public void setLeft(BSTNode left) { this.left = left; } /**  * Get the node to the right of this node.  *  * @return node to the right.  */  public BSTNode getRight() { return right; } /**  * Set the node to the right of this node.  *  * @param right new node to the right.  */  public void setRight(BSTNode right) { this.right = right; } }