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

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

       

Hint: the textbook has code for each of these methods. Please refer to them if you get stuck. You will probably adapt the code heavily to make it more OO, but it's still worth reading.

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

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