Trees - Data Structures and Problem Solving Using Java - page 669

Must we use recursion to implement the traversals? The answer is clearly
no because, as discussed in Section 7.3, recursion is implemented by using a
stack. Thus we could keep our own stack. 2 We might expect that a somewhat
faster program could result because we can place only the essentials on the
stack rather than have the compiler place an entire activation record on the
stack. The difference in speed between a recursive and nonrecursive algorithm
is very dependent on the platform, and on modern computers may well be
negligible. It is possible for instance, that if an array-based stack is used, the
bounds checks that must be performed for all array access could be signifi-
cant; the run-time stack might not be subjected to such tests if an aggressive
optimizing compiler proves that a stack underflow is impossible. Thus in
many cases, the speed improvement does not justify the effort involved in
removing recursion. Even so, knowing how to do so is worthwhile, in case
your platform is one that would benefit from recursion removal and also
because seeing how a program is implemented nonrecursively can sometimes
make the recursion clearer.

We can traverse
nonrecursively by
maintaining the
stack ourselves.

We write three iterator classes, each in the spirit of the linked list. Each
allows us to go to the first node, advance to the next node, test whether we
have gone past the last node, and access the current node. The order in which
nodes are accessed is determined by the type of traversal. We also implement
a level-order traversal, which is inherently nonrecursive and in fact uses a
queue instead of a stack and is similar to the preorder traversal.

An iterator class
allows step-by-step
traversal.

Figure 18.24 provides an abstract class for tree iteration. Each iterator
stores a reference to the tree root and an indication of the current node. 3
These are declared at lines 47 and 48, respectively, and initialized in the
constructor. They are protected to allow the derived classes to access them.
Four methods are declared at lines 22-42. The isValid and retrieve methods
are invariant over the hierarchy, so an implementation is provided and they
are declared final . The abstract methods first and advance must be provided
by each type of iterator. This iterator is similar to the linked list iterator
( LinkedListIterator , in Section 17.2), except that here the first method is
part of the tree iterator, whereas in the linked list the first method was part
of the list class itself.

The abstract tree
iterator class has
methods similar to
those of the linked
list iterator. Each
type of traversal is
represented by a
derived class.

2. We can also add parent links to each tree node to avoid both recursion and stacks. In this chap-
ter we demonstrate the relation between recursion and stacks, so we do not use parent links.
3. In these implementations, once the iterators have been constructed, structurally modifying
the tree during an iteration is unsafe because references may become stale.