Overview
Trees also offer user-friendly traversal via "iterators".
Like node removal, design and coding of the iterator tends to require a bit of tinkering. Don't be surprised if you run into a few stack overflows along the way...
Algorithms
There are different approaches for iteration, and you might invent your own.
Here are some references:
One Approach
In addition to the algorithm references listed above, here is another approach.
Here is the general idea:
- Use Stack only
- Stack holds "Nodes"
- Top of stack is "nextNode"
- Stack holds node "ancestors" where top-to-bottom of stack contains new-to-old node "ancestors" (root is oldest ancestor)
- Initialize iterator so it starts at "first" node (per inorder traversal)
- Advance iterator to "nextNode" before returning data in "next" method so iterator is always in "ready" state similar to linear structure iterators
- Iterator's hasNext returns true if stack is not empty
Hint: You know you will always be moving to right (or upward to ancestor) when advancing.