CSSE 230: Binary Search Tree Exercise - Part 1
This is the first part of a three part assignment. The other two parts
are about tree iterators and removing elements from a tree.
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.
- Create a new Java project, call it BST and install the following
BinarySearchTree.java file in it.
- You are not permitted to maintain pointers to parents in the
fields of your BinaryNode or BinarySearchTree classes.
- 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.
- 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.
- 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.
- Implement and test a method boolean isEmpty, which returns
TRUE if the tree is empty and FALSE otherwise. This method runs in
constant time.
- 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.
- Implement and test a int size() method which
returns the number of elements in the tree. This method runs in
constant time.
- 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.
- 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.
- Submit your BinarySearchTree.java file to the appropriate
dropbox on Moodle at 23:59 on day 7.