Implemented the Realty ADT using a binary search tree (BST), and implement an iterator so that it fulls the Set interface.
You will need to add a parent field to the Node class.
Then you need to check that they are set correctly. The easiest way to do so is to add a parameter to the checkInRange helper method that gives the expected parent field which then should be checked.
Then you will need to change "add" (or the placeUnder helper method) to update the parent link.
To assist with iterators, you will implement two private helper methods:
isInTree(Node) This method is used to check if the parameter node is actually in the tree. It also succeeds if the node is null. Your code shouldn't rely on the node having reasonable links: it could be in a little cyclic "tree" all by itself. The code can rely on this tree being well formed, so it knows that if the node is in the tree, it will be in a paricular spot.
getNextNode This method finds the next node in the tree in order. It should use parent pointers to be efficient. It should not start from the root as was done in getNext. Instead it should start at the node indicated.
In this assignment, you will be implementing the standard "Set" interface, using the helpful AbstractSet class. Sets are collections, and AbstractSet functions much like AbstractCollection. Thus, the most interesting method that needs to be implemented is the iterator.
You should implement the iterator method by creating a new instance of the MyIterator nested class. You should also make sure that all public methods that override something from AbstractSet are correctly marked override.
We will use the parent pointers and the new helper methods to implement an iterator. The iterator will keep track of the current node (so we know what to remove) and the next node (so we know what, if anything comes next). For fail-fast semantics, we will also keep a version in the main class and one with the iterator. Recall that the version must be updated whenever the number of elements changes, and that the iterator methods need to check the version to see if they are stale.
When an iterator is constructed, you will need to set up the next node so that it will be ready to go. Remember where to find the first in-order node in a binary search tree. Hint: it's rarely the root.
In order to implement the iterator remove() method, we will keep track of the current node in the iterator and then remove it from the tree. As usual, you should make sure you implement the hard removal process in only one place.
The activity this week explains how there are easier and harder cases for removal. In particular if the node has both left and right children, we have to replace it with either the greatest predecessor or the least successor. Since our remove method is within an iterator, we have to use the greatest predecessor so as not to disturb the running iterator's "next node." Before we perform this replacing, the greatest predecessor has to be removed from the tree first, but this is easy since it always classifies in the easier cases to remove (why?). Do not forget to update the size field and the versions so we have a fail-fast iterator.