4.21 Binary Search Tree

Implement a BinarySearchTree class which implements the BinarySearchTreeInterface interface and a BinarySearchTreeNode class which implements BinarySearchTreeNodeInterface. You should not modify the interfaces themselves.

All of the requirements/documentation are included in the comments in the interface classes. Note that in this implementation, the binary search tree node and the binary search tree will be implemented in separate java files (which is different from how we implemented them in class).

Tip

I highly recommend that you test often using the test file that I will provide on canvas. I put in a great deal of effort to provide meaningful error messages on failures, so I think that you'll find the test file to be helpful. The tests on zylabs should have the same error outputs.

Extra credit

You have a huge opportunity to get some extra credit on this assignment. The remove method is extra credit. There are 4 tests for the remove method and 10 tests for all of the other methods. All of the tests will be weighted equally which means that if you passed all of the tests, you would get 140% on this assignment. Some of the remove tests are actually pretty easy so even if you feel like you can't implement remove perfectly, implement some basic cases like removing a leaf node. I recommend you save removing the root node for last because it is the most difficult test to pass.

Interfaces

The interfaces you must implement (and submit because apparently zybooks won't let me just automatically include them) are include below. I'll also post them on canvas.

BinarySearchTreeInterface.java

import java.util.List; /** * Basic interface for the binary search tree. * * The student's implementation must implement each of these * methods, plus a default constructor * * @param  */ public interface BinarySearchTreeInterface> { /** * The method returns the root node of the tree. This is not a standard binary tree operation, * however, by giving public access to the tree node structure, this allows the zylabs unit tests * to give you much better feedback about any differences between your tree and the expected * results. * @return The root containing the entire tree (or null for an empty tree) */ public BinarySearchTreeNodeInterface getRoot(); /** * Adds the specified item to the tree (if it does not already exist) * @return true if the item was added, otherwise, false */ public boolean add(E value); /** * @param value value to look for * @return true if and only if the value is contained within the tree */ public boolean contains(E value); /** * Clears the BST */ public void clear(); /** * @return the size of the tree */ public int size(); /** * Depth is the maximum number of edges between the root and any of its ancestors * @return the height of the tree */ public int height(); /** * @return list representing data in an in-order traversal */ public List getDataInOrder(); /** * @return list representing data in a pre-order traversal */ public List getDataPreOrder(); /** * @return list representing data in a post-order traversal */ public List getDataPostOrder(); /** * Extra credit * 

 * Remove the specified item from the tree if it exists. * I'm going to be pretty generous with the extra credit on this one * so even if you don't think you can implement a complete remove method, * try to implement the easy cases (such as removing a leaf node). There will * be mulitple extra credit zylabs tests and some of them will be easier than others. * 

 * For the case of removing an internal node with two children, there are two algorithms * that work: replacing the node to remove with the smallest node on the right subtree or * replacing the node to remove with the largest node on the left subtree. Both of these * approaches are technically correct, however, you must choose the first option (removing * the smallest node on the right subtree) in order to pass the tests and get credit. * @param value value to remove * @return true if the value was present in the tree, false otherwise */ public boolean remove(E value); } 

BinarySearchTreeNodeInterface.java

/** * * Represents a node within the binary search tree. * @param  The type of data that will be contained within each node */ public interface BinarySearchTreeNodeInterface> { /** * @return the data contained within this node */ public E getData(); /** * @return this nodes left child, or null if there is none */ public BinarySearchTreeNodeInterface getLeft(); /** * @return this nodes right child, or null if there is none */ public BinarySearchTreeNodeInterface getRight(); } 

Please go off of the above code and i need the extra credit.