Programming Assignment:
Binary Search Trees

Objectives

The purpose of this exercise is to learn about how to implement binary trees and binary search trees, how to design and implement tree iterators, and how to perform traversals of trees. Another purpose is to practice recursion.

You may share ideas with classmates, but you must write your own code.

Instructions

Starting the project

Make sure you read each specification here before writing code. There are lots of hints contained in this document.

Checkout the BinarySearchTree project from your individual repository.

Make sure you understand the given code in the basic BinarySearchTree and BinaryNode classes. They use parameterized generics with type parameter T. BinaryNode is an inner class since other classes won't use it directly.

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.

Notes: Style and documentation requirements

1. Please ensure that your code is concise and well written.
2. You are not permitted to maintain pointers to parents in the fields of your BinaryNode or BinarySearchTree classes.
3. [5 pts] You must have Javadoc comments, plus other internal comments for longer methods or things that aren't obvious to you at first.
4. [10 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.
5. 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.

Milestone One: BinaryTree methods

The following methods don't assume that the elements are stored in sorted order, so work for any BinaryTree, not just BSTs.

1. Implement the following methods. The BSTManualTesting.java file contains "manually-built" unit tests, since we have not yet implemented the insert() method.
   • A recursive int height() method which returns the height of the tree. If the tree is empty, return -1. The recursion will happen in the BinaryNode class in this method and others.
   • A recursive int size() method which returns the number of elements in the tree.
   • A recursive boolean containsNonBST(item) method that returns true if and only if the item is in the tree.
   • A boolean isEmpty() method, which returns true if the tree is empty and false otherwise.
   • A recursive String toString() method which returns a String containing the elements of the tree.
   • An ArrayList<Object> toArrayList() method which returns an ArrayList of the elements in-order.
   • An Object[] toArray() method which returns an array of the elements in-order. (Note: toArrayList() can help with this if you find a method which converts ArrayLists to Arrays.)
   • Three iterators. Make each an inner class of BinarySearchTree and take advantage of the access rights that come with inner classes. Each must throw a NoSuchElementException if the iterator has no more elements.
     1. An ArrayListIterator that calls the toArrayList() method and iterates over the list. This iterator should be returned when you call the public Iterator inefficientIterator() method. This is NOT a lazy iterator.
     2. A lazy iterator that performs pre-order traversal. This iterator should be returned when you call the public Iterator preOrderIterator() method.
     3. A lazy iterator that performs in-order traversal. This iterator should be returned when you call the public Iterator iterator() method.
     4. Make your BinarySearchTree class iterable (by declaring that it implements the Iterable<T> interface.)

Milestone Two: BST methods

1. [5 pts] Ensure that your BinarySearchTree class is properly parameterized to accept only Comparables. See the code in the day 12 slides for an example if you need one. One exception: toArray() must still return an array of type Object[], not T[]. This is according to the Java spec. For sample usage, refer back to comparingShapes in the WarmupAndStretching assignment. This contains a few more more hints related to maintaining NULL_NODEs in your code that I used to give (some may no longer apply).
2. Implement the following methods:
   1. A  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. It will call a recursive BinaryNode method.
   2. 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. 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. (Note: this is also a good way to implement insert so it returns a boolean.)
   3. A boolean contains(T item) method. You already wrote an contains for arbitrary trees. Now go back and write a method to take advantage of the fact that your tree is a BST. You should notice that it is much more efficient - why is this so? 
   4. Notes: The recursive BinaryNode insert() and delete() in the text return BinaryNodes. So how do the BinarySearchTree methods return Booleans? Here are some ideas:
      1. Could you return 2 things? Yes, if you create a simple composite class to hold both a boolean and a BinaryNode.
      2. Could you pass and mutate a parameter? Parameters are call-by-value, so primitives cannot be mutated. So define a class for and pass a simple "BooleanContainer" object so you can mutate the Boolean inside. This is what I did.

Milestone 3: Other methods

1. 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. (How can you detect this?)
2. Implement the void remove() method in both of the lazy iterators. Hint: Just call BST remove(). But throw exceptions if next() hasn’t been called, or if remove is called twice in a row. Look at the documentation of the remove method from java.util.Iterator for details to make sure you throw the proper exceptions in each case.

Turn-in Instructions

Review the Style and Documentation Requirements above to make sure your code meets them.

Points: 120 for total of unit tests, 20 for style and documentation.

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).