Assignment 09

Task

Expand a BST implementation. The BST ADT should behave much like a sorted list.

Text: 6.4
Concepts: binary search trees (BSTs), (iterators).

Steps

Here is the BinarySearchTree class covered in lecture (with modified toString()):

Expand this implementation with the following additions:

Add a constructor that takes a java.util.Collection

In the constructor, create a List from the Collection, shuffle the list, and then build the new tree with the elements of the list. Shuffling the collection in this way means that, most of the time, the resulting BST should be fairly balanced, even if the collection was sorted. You need to make a List copy of the passed Collection because 1) only lists can be shuffled, and 2) making a copy first means the shuffling won't affect the order of the originally-passed collection.

Add a public String toFullString() method

The existing toString() method shows the contents in a fairly standard Collections format. Add a toFullString() method that also shows the full tree structure. This should be a multi-line string with one node per line. The nodes should be listed in pre-order traversal order. Each node should be prefaced by a series of < and > characters showing the path (left and right) that leads from the root to that node. (Hint: You can accomplish this recursively in O(n) with a String prefix parameter that you extend by one character with each successive call.)

As an example, consider this tree:

Printing the results of toFullString() should give:

|15
|<12
|<<10
|<<>11
|>18
|><16
|><>17
|>>20

The | characters are optional. The method should not change or destroy the tree.

Make the BST Iterable

That is, implement the java.lang.Iterable interface. This means you will also need to implement an associated java.util.Iterator. I recommend writing this as a nested class, just as was done in A06's LinkedList.

This iterator should give an in-order traversal that eventually returns all the elements of the BST in sorted order according the elements' "natural ordering" (normally smallest to largest). This is the same order as returned by toString().

You should implement all 3 iterator methods. Don't forget to read the API to see what your methods need to do. For example, you may need to throw a NoSuchElementException or an IllegalStateException in some situations.

Feel free to modify the existing method implementations if you need to. Don't forget to add another @author tag with your name to the class documentation.

Also write and include a UsernameA09.java file with a main method that tests your implementation.

What to Submit

Create a .jar file named UsernameA09.jar. This should include:

TreeNode.java
BinarySearchTree.java
UsernameA09.java

Upload your UsernameA09.jar to Tamarin.

Remember to follow the course coding standards on all assignments.

Grading [50 points]

5 - Compiles
5 - BinarySearchTree(Collection) constructor
15 - toFullString()
3 - Iterable: Required for Iterator points.
20 - Returned Iterator: hasNext (3), next (11), and remove (6).
In cases of equal elements, +3 if remove actually removes the node of the element most recently returned by next().
2 - UsernameA09

Discussion

remove() and Questions of Equality

It is possible to reuse the existing BST remove method from your iterator. (This is not the most efficient implementation, but it is easy to write and the performance is still pretty good.) This should be safe because your iterator will usually be removing the element returned by the last call to next(). (Remember that you'll have to throw an exception if next() has not been called yet or if the previously returned item has already been removed.) That means that the node to remove will usually be "behind" the iterator, either as a left child or as a parent. For example:

If the iterator just returned 5, calling remove() or not does not affect which node the iterator should return next. It will still return 7 next. That makes things easier.

However, equal values make the situation a little trickier. Consider:

Suppose we build a new iterator for this tree, call next() three times (giving 3, 4, 5), and then call remove(). Before the remove:

      6
     / \
    5   7
   /
  4
 / \
3   5  (last value returned by iterator in bold)
   /
  5

If we call the BST's remove method to do the removal work, it will encounter the top 5 first and delete that one, which will pull the 4 (and subtree) up to replace it:

This is a little weird, but, if we truly cannot discriminate between the different 5 values, we will not be able to detect this sleight-of-hand from outside of the BST ADT (except for toFullString()). (We'll talk more in a couple weeks about the different notions of equality in Java. In brief, testing for equality with .compareTo, .equals, and == can give you different answers depending on the specific types involved.) Interestingly, the removed 5 will still get processed by the iterator because it is already in your iterator's stack. So calling next() two more times still returns gives two more 5s.

Although your iterator's abstract behavior should not be affected by equal values, it would be nice to actually delete the expected node in order to preserve the expected tree structure. If you want to implement your iterator's remove method so that it always removes the node of the element actually returned by the last call to next(), I'll give you +3 EC.

FAQs

Related to the BST constructor, what do you mean "create a List from the Collection"?

public BinarySearchTree(Collection<E> col) {
  List<E> list = new ArrayList<E>(col);
  //...
}

What are we supposed to print in UsernameA09?

That's up to you. You definitely need to test your new BST methods and iterator, though. At the very least, you should create a sample BST object, call your new methods on it, and confirm that their results are correct.

You need to submit a compilable UsernameA09.java file in your submission, even if it just has an empty main method. This is because Tamarin requires a file of that name in your JAR in order to start grading. (I plan to change this Tamarin requirement in future, but that won't likely happen this semester.)

How do I use recursion to implement the Iterator's next() method?

You really shouldn't try to. Although we discussed some different approaches to this, a simple (and thus elegant) design does not involve recursion. This is because recursion has to process all the nodes at once in a single (repeated) method call. But your iterator's next() method needs to return one node at a time, yet still resume where it left off in its traversal. Although you can mark nodes as visited and use recursion to retrace your way through the tree to the last node you returned, this is not very efficient. Also, if you have only a simple boolean "visited" variable in your nodes, you will run into bugs if you have more than one iterator at a time.

Instead, I suggest you use a stack in your iterator. This stack will serve the same purpose as the runtime stack does in recursion: to keep track of where you are in the process--ie, which node you're on and how you got here for backtracking purposes. So your iterator needs an internal stack of TreeNodes as an instance variable. (You can use a java.util.Deque for this, or the Stack class from earlier assignments.) You'll create this Stack in your iterator constructor and load it with the root node (if any) and all of root's left descendants. Then in each call to next(), you'll pop off a node from this stack and process it. Again, there is (brief) help on what should go in each method in the lecture slides.

Note that the assignment requirements specify only the iterator's behavior, not its implementation, so you are not required to use this stack-based approach.

I still don't really get this stack thing with the iterator.

Your iterator needs only two instance variables: a stack of TreeNodes and a last variable that records whether next() has returned something. This can be either an E or a TreeNode variable that is initially null.

When you build an iterator, its constructor should load the stack with the root and all of its left descendants.

Given the following tree:

your iterator would start off like this:

  last: null
  stack: 6, 2, 1  (listed bottom to top)

When you call next(), the next node to return (if any) is on the top of the stack. Before you return it, check whether it has a right child. If so, push the right child and all of its left descendants.

Thus, if we call next() seven times on our iterator, it will go through these states:

  last: 1
  stack: 6, 2

  last: 2
  stack: 6, 5, 4, 3

  last: 3
  stack: 6, 5, 4

  last: 4
  stack: 6, 5

  last: 5
  stack: 6

  last: 6
  stack: 7

  last: 7
  stack: [empty]

Note how the sequence of values that pass through the last variable correspond to an in-order traversal of the tree. In your remove method, you'll need to check your last variable to see what to remove. Don't forget to throw an exception if last is null, or to set it to null after removing the corresponding element.

I have a nested Iterator class. How do I call the remove(E) method in the BST?

You may have a line like this in your iterator:

  remove(last);

but get an error like:

The method remove() in the type BinarySearchTree<E>.BSTIterator 
is not applicable for the arguments (E)

In order to refer to the remove method in the enclosing class, you'll need:

  BinarySearchTree.this.remove(last);

The notation is a little weird, but this refers to the remove instance method in the enclosing BinarySearchTree class.

I used the code given above, but I still can't call BST's remove method because I get a compiler error.

On Java 6, the error message is quite unhelpful:

BinarySearchTree.java:230: cannot find symbol
symbol  : method remove(E)
location: class BinarySearchTree<E>
      BinarySearchTree.this.remove(lastNode.getData());

This is confusing because there is totally a remove(E) method in the BinarySearchTree class!

The error message from the Java 7 compiler is much more helpful:

BinarySearchTree.java:230: error: no suitable method found for remove(E#1)
      BinarySearchTree.this.remove(lastNode.getData());
                           ^
    method BinarySearchTree.remove(E#2,TreeNode<E#2>) is not applicable
      (actual and formal argument lists differ in length)
    method BinarySearchTree.remove(E#2) is not applicable
      (actual argument E#1 cannot be converted to E#2 by method invocation conversion)
  where E#1,E#2 are type-variables:
    E#1 extends Object declared in class BinarySearchTree.BinarySearchTreeIterator
    E#2 extends Comparable<E#2> declared in class BinarySearchTree

This gives a much better clue as to what is going on. Specifically, as the error message shows (especially in the last two lines), there are two variables named E here: one (E#1) in the nested iterator class and one (E#2) in the BST class. This is because you have accidentally redeclared the type parameter in an incompatible way.

To review, you have one E type parameter declared in the BST class. You declare a type parameter and its bounds by listing it after the name of the class you are defining:

public class BinarySearchTree<E extends Comparable<E>> implements Iterable<E> {

This is good: E is some kind of Comparable item.

But then, in your nested class BSTIterator class, you probably have this:

  public class BinarySearchTreeIterator<E> implements Iterator<E>{
     
    private TreeNode<E> lastNode;

Because you have <E> after the name of the class you are defining, you're declaring another (different) E variable here. This E hides the first one. This second E has no bounds to it, so it is only of type Object. (The <E>s after Iterator and TreeNode are not declarations; those are uses of the E: the Iterator and TreeNode will return/contain the same type as whatever goes into a BinarySearchTreeIterator. The syntax difference between type parameter declaration and use is, admittedly, very subtle.)

Therefore, after compile-time type erasure, the line:

  lastNode.getData();

gets an Object out of a TreeNode. But this means that you are then trying to pass an Object to the remove(E) method in the BST class... but the E in the BST class is a Comparable object (after type erasure)! So you're basically trying to pass an Object to remove(Comparable), which is why you get a compile error.

The fix: Don't redeclare the E in the nested class. Change your BSTIterator declaration line to:

  public class BinarySearchTreeIterator implements Iterator<E>{

So there's no <E> after BSTIterator now. You're still using the first E (from the enclosing BST) to describe what type is returned by the Iterator, but you're not redeclaring a second E.

This was a tricky one!

[New] How do I implement toFullString()? The angle-bracket prefix part is giving me trouble.

I recommend you write a recursive helper method that will do a pre-order traversal. However, besides just passing the current TreeNode to process, also include a parameter that specifies the prefix:

  private String toFullString(TreeNode<E> node, String prefix) {

When you first call this method, you can pass it the root node and "|" (or just an empty String).

Then, while doing the traversal, whenever you go left, you can make a recusive call, passing node.getLeft() and the current prefix + "<" as arguments. And when you go right, pass node.getRight() and prefix + ">".