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

iteration and can set current to null and return. (If current is already null , we
have advanced past the end, and an exception is thrown.) Otherwise, we
repeatedly perform stack pushes and pops until an item emerges from the
stack for a third time. When this happens, the test at line 22 is successful and
we can return. Otherwise, at line 24 we push the node back onto the stack
(note that the timesPopped component has already been incremented at line
22). We then implement the recursive call. If the node was popped for the first
time and it has a left child, its left child is pushed onto the stack. Likewise, if
the node was popped for a second time and it has a right child, its right child
is pushed onto the stack. Note that, in either case, the construction of the
StNode object implies that the pushed node goes on the stack with zero pops.
Eventually, the for loop terminates because some node will be popped for
the third time. Over the entire iteration sequence, there can be at most 3 N
stack pushes and pops, which is another way of establishing the linearity of a
postorder traversal.

18.4.2 inorder traversal

The inorder traversal is the same as the postorder traversal, except that a node
is declared visited after it is popped a second time. Prior to returning, the iter-
ator pushes the right child (if it exists) onto the stack so that the next call to
advance can continue by traversing the right child. Because this action is so
similar to a postorder traversal, we derive the InOrder class from the PostOrder
class (even though an IS-A relationship does not exist). The only change is the
minor alteration to advance . The new class is shown in Figure 18.28.

Inorder traversal
is similar to
postorder, except
that a node is
declared visited
when it is popped
for the second time.

18.4.3 preorder traversal

The preorder traversal is the same as the inorder traversal, except that a node
is declared visited after it has been popped the first time. Prior to returning,
the iterator pushes the right child onto the stack and then pushes the left child.
Note the order: We want the left child to be processed before the right child,
so we must push the right child first and the left child second.
We could derive the PreOrder class from the InOrder or PostOrder class, but
doing so would be wasteful because the stack no longer needs to maintain a
count of the number of times an object has been popped. Consequently, the
PreOrder class is derived directly from TreeIterator . The resulting class with
implementations of the constructor and first method is shown in
Figure 18.29.

Preorder is the
same as postorder,
except that a node
is declared visited
the first time it is
popped. The right
and then left chil-
dren are pushed
prior to the return.