CSSE 230: Binary Search Tree Exercise - Part 1

Please work on this exercise by yourself.

For this portion, you will focus on inserting into a tree as well as a few support methods.

1. Create a new Java project, call it BST and install the following BinarySearchTree.java file in it.
2. You are not permitted to maintain pointers to parents in the fields of your BinaryNode or BinarySearchTree classes.
3. Ensure that you use parameterized generics whenever possible. Ensure that your BinarySearchTree class is properly parameterized to accept only Comparables. Furthermore ensure that BinarySearchTree implements the parameterized "Iterable" interface.
4. Ensure that your BinaryNode class as well as the iterators are inner classes and that your code takes advantage of the access rights that come with inner classes.
5. Add a recursive insert method with the following signature: boolean insert(T o). (Assuming that your parameterized Comparator interface is named "T".) This method has to throw an IllegalArgumentException if you pass it a null argument. It has to return true if the tree was modified and false otherwise. The insert method should maintain a Binary Search Tree. The recursion takes place in the BinaryNode class. This method has a worst-case performance of N.
6. Implement and test a method boolean isEmpty, which returns TRUE if the tree is empty and FALSE otherwise. This method runs in constant time.
7. Implement and test a recursive int height() method which returns the height of the tree. If the tree is empty, return -1. This method runs in linear time.
8. Implement and test a int size() method which returns the number of elements in the tree. This method runs in constant time.
9. Review your code and ensure that it is well written. Look for places where you can simplify through code reuse and other methods. Among others, none of the methods in the BinarySearchTree class proper should be recursive. Recursion should only take place in the BinaryNode class proper. Notice that the size method should simply return the value of a size field that is maintained in the BinarySearchTree class and is increased everytime you successfully insert an element into the tree. Ensure that your code follows true OO-style, i.e. the key methods should be such that you do not pass in the object to which you apply a method. Finally, ensure that there is no spagetti code. Ensure that your iterators are lazy, i.e. they do not preprocess the entire BST. The Testing.java code needs to run with the getters and setters disabled. As a matter of fact you should remove the setters. You are not permitted to use a static BinaryNode null node, instead, use "null" outright.
10. Use the following JUnit test suite to test your code. Some of the test-cases are about things we will introduce next time. I will eventually add more test cases.
11. Submit your BinarySearchTree.java file to the appropriate dropbox on Moodle at 23:59 on day 7.