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.

Download the BinarySearchTree project from your the github classroom link

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.

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 in-order 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 size() method which returns the number of elements in the tree.
   • 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 boolean isEmpty() method, which returns true if the tree is empty and false otherwise.
   • A recursive boolean containsNonBST(item) method that returns true if and only if the item is in the tree.
   • 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. Make your BinarySearchTree class iterable by adding "implements Iterable<T>" interface to the class declaration. This will cause red squiggly marks to appear under BinarySearchTree, use Eclipse to add the unimplemented Iterator methods to the BinarySearchTree class (it will add method iterator(), which you'll implement in Step #4 below).
     2. An ArrayListIterator that calls the toArrayList() method and iterates over the list.
        It's recommend that you click Eclipse's menu bar: File | New | Class - When the New Java Class dialog appears then (1) check Enclosing type (make sure it specifies BinarySearchTree); (2) name the class ArrayListIterator; (3) Modifiers: click private (to make it a private subclass of BinarySearchTree); (4) Interfaces: java.util.Iterator<T> (you might have to put the 'T' between the angle brackets)
        An instance of this iterator should be returned by BinarySearchTree's public Iterator<T> inefficientIterator() method - you must add this method to BinarySearchTree. This is NOT a lazy iterator.
     3. A lazy iterator that performs pre-order traversal.
        An instance of this iterator should be returned by BinarySearchTree's public Iterator<T> preOrderIterator() method - you must add this method to BinarySearchTree.
     4. A lazy iterator that performs in-order traversal.
        This iterator should be returned by BinarySearchTree's public Iterator<T> iterator() method (which as added to your class in Stem #1 above)

Milestone Two: BST methods

1. [5 pts] Ensure that your BinarySearchTree class is properly parameterized to accept only Comparables. See the code in the slides (on the day we discuss BST delete) 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. Make sure you get insert correct, as all the other tests depend on it!
   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 in-order predecessor (i.e., 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 adding, committing, and pushing the edited files to the Git server. (We recommend committing/pushing often, whenever you have made some progress toward a solution to one of the problems.)