5.13 Binary Search Tree Implement a BinarySearchTreelt;Egt; class which implements the BinarySearchTreeInterfacelt;Egt; interface and a

5.13 Binary Search Tree

Implement a BinarySearchTree<E> class which implements the BinarySearchTreeInterface<E> interface and a BinarySearchTreeNode<E> class which implements BinarySearchTreeNodeInterface<E>. 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).

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.

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.

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.