Q: Do integer set classes need to implement the IntIterator interface and provide methods for hasNext and next ?
A: No! Definitely not. That would be an ``internal iterator.'' The iterator you define should be an external iterator, like the STL iterators: you should be able to have multiple iterators running at the same time.
Q: How can the iterator object get access to the internal nodes of the structure; do we need to provide some more methods?
A: No. Make the iterator class that implements IntIterator a nested class so it can access the data structure directly.
Q: Is it OK if the iterator returns elements in a non-sorted order?
A: Yes. Otherwise, the oterator for the linked or hashed int set would be very inefficient.