Extend the BinaryTreeClass to implement the Iterable interface by providing an i
ID: 3818458 • Letter: E
Question
Extend the BinaryTreeClass to implement the Iterable interface by providing an iterator. The iterator should access the tree elements using an inorder traversal. The iterator is implemented as a nested private class. (Note: unlike Node, this class should not be static.)
Design hints:
You will need a stack to hold the path from the current node back to the root. You will also need a reference to the current node (current) and a variable that stores the last item returned.
To initialize current, the constuctor should start at the root and follow the left links untill a node is reached that does not have a left child. This node is the initial current node.
The remove method can throw an UnsupportedOperationException. The next method should use the following algorithm:
1. Save the contents of the current node.
2. IF the curent node has a right child
3. push the current node onto the stack
4. set the currrent node to the right child
5. while the current node has aleft child.
6. push the current node into the stack
7. set the current node to the left child
8. Else the current node does not have a right child
9. while the stack is not empty and
the top node of the stacks right child is equal to the current node
10. set the current node to the top of the stack and pop the stack
11. IF the stack is empty
12. set the current node to null indicating the iteration is complete
13. ELSE
14. set the current node to the top of the stack and pop the stack
15. return the saved contents of the initial current node.
Explanation / Answer
Iterator Example without Generics
Iterator Example using Generics
ConcurrentModificationException
Look at the following code, it throws ConcurrentModificationException. We cannot add or remove elements to the underlying collection when we are using an iterator.
Implementing our own Custom Iterator
We will create our own custom class and make it implement Iterable, so that it returns an Iterator using which we can iterate the elements.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.