Complete the public methods for the BST class. You may add any private helper methods required to make the BST work. TreeNode.java package cp213; /** * The individual node of a linked structure that stores {@code T} objects and a * count. This is a doubly-linked node with left and right pointers to child * nodes. The node link can be updated, but not the node data, in order to avoid * moving data between nodes. Data structures must be reordered by moving nodes. * * @author David Brown * @version 2017-11-02 */ public class TreeNode> { // The T data and count. private T data = null; private int count = 1; // Link to the child TreeNodes. private TreeNode left = null; private TreeNode right = null; private int height = 1; /** * Creates a new TreeNode with data and null links to its child TreeNodes. * Not copy safe as it accepts a reference to the data rather than a copy of * the data. * * @param data * The data to store in the node. */ public TreeNode(final T data) { this.data = data; } /** * Decrements the data count of this TreeNode by 1. */ public void decrementCount() { this.count--; } /** * Returns the data count of this TreeNode. * * @return count. */ public int getCount() { return this.count; } /** * Returns this TreeNode data. Not copy safe as it returns a reference to * the data, not a copy of the data. * * @return The data portion of this TreeNode. */ public T getData() { return this.data; } /** * Returns a DataCountPair version of the node. This contains only the data * and count, and not the links to child nodes. * * @return A new DataCountPair object. */ public DataCountPair getDataCountPair() { return new DataCountPair<>(this.data, this.count); } /** * Returns the height of this TreeNode. * * @return height. */ public int getHeight() { return this.height; } /** * Returns the left child of this TreeNode. * * @return left. */ public TreeNode getLeft() { return this.left; } /** * Returns the right child of this TreeNode. * * @return right. */ public TreeNode getRight() { return this.right; } /** * Increments the data count of this TreeNode by 1. */ public void incrementCount() { this.count++; } /** * Updates the left child reference of this TreeNode to another TreeNode. * * @param left * The new TreeNode to link to. */ public void setLeft(final TreeNode left) { this.left = left; } /** * Updates the right child reference of this TreeNode to another TreeNode. * * @param right * The new TreeNode to link to. */ public void setRight(final TreeNode right) { this.right = right; } @Override public String toString() { return "V: " + this.data + "; C: " + this.count + "; H: " + this.height; } /** * Updates the height of this TreeNode to 1 plus the maximum heights of its * two child nodes. Empty child nodes have a height of 0. */ public void updateHeight() { int leftHeight = 0; int rightHeight = 0; if (this.left != null) { leftHeight = this.left.height; } if (this.right != null) { rightHeight = this.right.height; } this.height = Math.max(leftHeight, rightHeight) + 1; return; } } 

BST

package cp213; import java.lang.reflect.Array; /** * Implements a Binary Search Tree. * * @author your name here * @version 2017-11-02 * * @param  * The data to store in the tree. */ public class BST> { // Attributes. protected TreeNode root = null; protected int size = 0; /** * Determines if this BST contains key. * * @param key * The key to search for. * @return true if this BST contains key, false otherwise. */ public boolean contains(final T key) { # your code here } /** * Determines if this BST is empty. * * @return true if this BST is empty, false otherwise. */ public boolean empty() { # your code here } /** * Returns the height of the root node of this BST. * * @return height of root node, 0 if the root node is null. */ public int getHeight() { # your code here } /** * TESTING ONLY. Returns the root node of this BST. The tree nodes should * not normally be visible outside the tree. Required for the * {@code DrawTree} class. * * @return the root node. */ public TreeNode getRoot() { return this.root; } /** * Returns the number of nodes in the BST. * * @return size of this BST. */ public int getSize() { return this.size; } /** * Determines whether two BSTs are identical. * * @param that * The BST to compare this BST against. * @return true if this BST and that BST contain nodes that match in * position, value, count, and height, false otherwise. */ public boolean equals(final BST that) { # your code here } /** * Inserts data into this BST. * * @param data * Data to store. */ public void insert(final T data) { # your code here } /** * Retrieves the data matching key and its count in this BST. * * @param key * The key to look for. * @return A DataCountPair object that contains the data that matches key * and its count, null otherwise. */ public DataCountPair retrieve(final T key) { # your code here } /** * TESTING ONLY. Returns an array of data from a linked data structure. Not * thread safe as it assumes contents of data structure are not changed by * an external thread during the copy loop. If data elements are added or * removed by an external thread while the data is being copied to the * array, then the declared array size may no longer be valid. The array * contents are in level order. * * @return an array of {@code DataCountPair} objects containing data of type * {@code T}. Returns null if the data structure is empty. */ @SuppressWarnings("unchecked") public final DataCountPair[] toArray() { DataCountPair[] array = null; if (this.root != null) { // Create an array of tree nodes based upon the class of an empty // DataCountPair object. array = (DataCountPair[]) Array .newInstance(new DataCountPair<>().getClass(), this.size); int i = 0; TreeNode node = null; final Queue> nodes = new Queue<>(); nodes.insert(this.root); while (!nodes.isEmpty()) { node = nodes.remove(); array[i++] = node.getDataCountPair(); if (node.getLeft() != null) { nodes.insert(node.getLeft()); } if (node.getRight() != null) { nodes.insert(node.getRight()); } } } return array; } /** * Determines if this BST is a valid BST; i.e. a node's left child data is * smaller than its data, and its right child data is greater than its data. * The height of a node is equal to the maximum of the heights of its two * children (missing child nodes have a height of 0), plus 1. * * @return true if this BST is a valid BST, false otherwise. */ public boolean valid() { # your code here } }