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

18.4.1 postorder traversal

The postorder traversal is implemented by using a stack to store the current
state. The top of the stack will represent the node that we are visiting at some
instant in the postorder traversal. However, we may be at one of three places
in the algorithm:

Postorder traversal
maintains a stack
that stores nodes
that have been vis-
ited but whose
recursive calls are
not yet complete.

1. About to make a recursive call to the left subtree

2. About to make a recursive call to the right subtree

3. About to process the current node

Consequently, each node is placed on the stack three times during the
course of the traversal. If a node is popped from the stack a third time, we can
mark it as the current node to be visited.

Otherwise, the node is being popped for either the first time or the second
time. In this case, it is not yet ready to be visited, so we push it back onto the
stack and simulate a recursive call. If the node was popped for a first time, we
need to push the left child (if it exists) onto the stack. Otherwise, the node was
popped for a second time, and we push the right child (if it exists) onto the
stack. In any event, we then pop the stack, applying the same test. Note that,
when we pop the stack, we are simulating the recursive call to the appropriate
child. If the child does not exist and thus was never pushed onto the stack,
when we pop the stack we pop the original node again.

Each node is
placed on the stack
three times. The
third time off, the
node is declared
visited. The other
times, we simulate
a recursive call.

Eventually, either the process pops a node for the third time or the stack
empties. In the latter case, we have iterated over the entire tree. We initialize
the algorithm by pushing a reference to the root onto the stack. An example of
how the stack is manipulated is shown in Figure 18.25.
A quick summary: The stack contains nodes that we have traversed but
not yet completed. When a node is pushed onto the stack, the counter is 1, 2,
or 3 as follows:

When the stack is
empty, every node
has been visited.

1. If we are about to process the node's left subtree

2. If we are about to process the node's right subtree

3. If we are about to process the node itself

Let us trace through the postorder traversal. We initialize the traversal by
pushing root a onto the stack. The first pop visits a . This is a 's first pop, so it is
placed back on the stack, and we push its left child, b , onto the stack. Next b is
popped. It is b 's first pop, so it is placed back on the stack. Normally, b 's left
child would then be pushed, but b has no left child, so nothing is pushed. Thus
the next pop reveals b for the second time, b is placed back on the stack, and
its right child, d , is pushed onto the stack. The next pop produces d for the first