Why Write Iterative Traversals

Recursion keeps the waiting nodes on the call stack for us, which is why the recursive traversals are only a few lines. So why replace the call stack with a stack of our own?

One reason is practical. A recursive traversal’s depth is bounded by the call stack, and a very tall tree can overflow it. A stack we build ourselves lives in the heap (the region of memory where Java stores the objects you create with new, which is much larger than the call stack), so it can grow much larger. But the main reason is that an iterator needs it.

In the iterator chapter we made a collection usable in an enhanced for loop by writing an iterator, an object whose next hands back one element and returns, so the loop body can run between elements. When next is called again, the iterator has to resume from the same place.

The recursive traversal cannot do that. Once you call the recursive preOrder, it visits every node before it returns. Java manages the call stack, so you cannot stop the recursion partway and resume it later.

To give a tree an iterator, you have to hold the waiting nodes in a stack you own, so the traversal can stop after producing one value and continue from the same stack. The problems that follow take the first step: each one rewrites a recursive traversal as a loop over a stack you manage yourself.