In Java: Please read the bolded rules carefully. Will rate and leave good review, thanks!

Here is the code provided for the class.

import java.util.Arrays; public class BSTree> { private static class Node> { public T data; public Node left, right;

public Node(Node left, T data, Node right) { this.left = left; this.data = data; this.right = right; }

public boolean contains(T d) { int comp = d.compareTo(data); if (comp == 0) return true; // Already in tree if (comp

} public int size() { // We know there is a node here int total = 1; // This node may have left children if (left != null) total = total + left.size(); // This node may have right children if (right != null) total = total + right.size(); // The total size of the tree from this point... return total; } public Node delete(T d) { int comp = d.compareTo(data); if (comp == 0) return deleteNode(); if (comp

private Node root;

public BSTree() { root = null; }

/** * Adds data to the tree if it didn't already contain it. * * @param data */

public boolean contains(T data) { if (root == null) return false; return root.contains(data); } public int size() { if (root == null) return 0; return root.size(); } public void delete(T data) { if (root == null) return; root = root.delete(data); } public T findByOrder(int k) { // TODO: Implement. return null; } }

The following methods should be implemented for BSTree. Begin with BSTree.java available on Canvas. You will probably have to implement corresponding helper Node methods! Do not add any data (variable) members to the BSTree/Node class, only methods (helper methods OK). For full credit, implement all methods without using new or creating arrays. (5 point penalty per method for using new/creating arrays) 3. Implement public T findByOrder(int k) Consider the sorted order of all the elements in the tree. The index of the smallest element is 0. The index of the largest element is tree.size() - 1. In the above tree, tree.findByOrder(1) would return "D" and tree.findByOrder(4) would return "H". Return null if k is not a valid index