Programming Assignment:
Binary Search Trees

Objectives

The purpose of this exercise is to learn about how to implement trees, how to design and implement a tree iterator, and how to perform level order traversal of trees. Another purpose is to practice recursion.

Work on this exercise by yourself.

Check-out Instructions

Your work for this assignment should be done in the BinarySearchTree project inside Eclipse. Check out this project from your personal SVN repository for this course.

Your personal SVN repository URL is:

http://svn.csse.rose-hulman.edu/repos/csse230-201420-username

where username is your Rose-Hulman username. Recall that your SVN password may be different than your Rose-Hulman network password. Your SVN password should be unchanged from previous terms. If this is your first term with an SVN account at Rose-Hulman, then you should have received an email from root with your password.

If you are unable to remember or find your SVN password, please let your instructor  know and he/she will run a script to reset it to a new random string of characters or to a string that you specify.

Be sure to commit your work often as you make progress on these programs. This will help you recover from mistakes, power failures, and freak accidents.   What will be graded is what is in your repository, so do not forget to commit.

See the Using Subclipse instructions at the end of this page for more information on using your SVN repository.

 

 

Milestone One

For milestone one, please add the following functionality to the BinarySearchTree project, as found on svn.
  1. Implement basic BinarySearchTree and BinaryNode classes.
  2. Implement the following methods. You can test each using the following unit testcases. They assume that you have not implemented the insert() method.

Milestone Two

For milestone two, please add the following functionality to your BinarySearchTree project.
  1. A ArrayList<Object> toArrayList() method which returns an ArrayList of the elements in-order.
  2. A Object[] toArray() method which returns an array of the elements in-order. (toArrayList() can help do this!)
  3. (Optional warmup: an iterator that calls the toArrayList() method and iterates over the list. This iterator should be returned when you call the public Iterator arrayListIterator() method. This is NOT a lazy iterator.)
  4. A lazy iterator that performs pre-order traversal. This iterator should be returned when you call the public Iterator preOrderIterator() method.
  5. A lazy iterator that performs in-order traversal. This iterator should be returned when you call the public Iterator iterator() method.
  6. Both iterators have to throw a NoSuchElementException if the iteration has no more elements.
  7. Make your BinarySearchTree class iterable

Milestone Three

For this milestone, please add the following functionality to your BinarySearchTree project.
  1. You are not permitted to maintain pointers to parents in the fields of your BinaryNode or BinarySearchTree classes.
  2. Ensure that your toString() method of the BinarySearchTree class returns the elements of the tree inorder and according to the same specs as for the Java TreeSet class.
  3. [5 pts] Ensure that your BinaryNode class as well as the two iterators are inner classes and that your code takes advantage of the access rights that come with inner classes.
  4. Modify your iterators so that the next() methods throw a ConcurrentModificationException if the tree gets modified after you create the iterator and before you are done with it.
  5. [5 pts] Ensure that you use parameterized generics whenever possible. Call your type parameter T. Ensure that your BinarySearchTree class is properly parameterized to accept only Comparables. Furthermore ensure that BinarySearchTree implements the parameterized "Iterable<T>" interface. Note that the toArray() method from above must still return an array of type Object[], not T[]. This is according to the Java spec. Read this for some hints, especially if you are maintaining NULL_NODEs in your code.
  6. A recursive boolean insert(T o) method. Assume that you are inserting into a Binary Search Tree, and make sure you insert it in a place so that it continues to be a Binary Search Tree. Throw an IllegalArgumentException if you pass it a null pointer. It has to return true if the tree was modified and false otherwise. The recursion takes place in the BinaryNode class.
  7. [15 pts] 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.
  8. [5 pts] Add JavaDoc comments.
  9. Add a boolean remove(T element) method which returns true if the element was successfully removed. Throw an IllegalArgumentException if the element to remove is null. When removing a node with two children, replace its value with the largest element in its left subtree. Ensure that the recursion takes place in the BinaryNode class. Please notice that the recursive remove method in the BinaryNode class will have BinaryNode as a return type. You may not modify the BinaryNode class so that it maintains pointers to the parent node. Please ensure that your code is concise and well written. Furthermore ensure that your remove method in the BinaryTree/Node class is thread-safe when it comes to the return type. In other words, you cannot have some global variable which captures whether an element was successfully removed. We recommend that you add to the remove method of the BinaryNode class an additional, mutable parameter. (This is also a good way to implement insert so it returns a boolean.)
  10. Implement the void remove() method in both of the lazy iterators. Have a look at the documentation of the remove method as found in the Java Collections API. Ensure that you throw the proper exceptions.
  11. Add T get(T e) method. It returns the object e passed to it, if it occurs in the tree and null otherwise. Notice that this is a method that could be used to find elements in a tree. In real life, it would be more complex.

    Here are the unit test cases that we will use for scoring your software.

Turn-in Instructions

Turn in your work by committing it to your SVN repository. We recommend committing often, whenever you have made some progress toward a solution to one of the problems. Your last commit date will determine the status of your submission as on-time, early, or late (See the Late Days policy in the course syllabus).