The Cost of the Iterator

The work in every iterator operation is either a stack check or a call to pushLeftSpine, which follows a path down the tree. A path down the tree is at most $h$ edges long, where $h$ is the height of the tree, as we measured it in the tree chapter. Let $n$ be the number of values in the tree.

• Creating the iterator runs pushLeftSpine(root), which follows the left edges down from the root: $O(h)$.
• hasNext is a single isEmpty check: $O(1)$.
• next pops one node, then runs pushLeftSpine on its right child, another path down the tree: $O(h)$ in the worst case. In the trace, the call that produced 50 pushed 70 and 60.

The worst case does not happen on every call. Over the whole traversal, every node is pushed once and popped once, so visiting all $n$ values is $O(n)$, which is $O(1)$ per call to next. That is an amortized $O(1)$, the same kind of bound as the dynamic array’s add. There, an occasional add takes $O(n)$ time to grow the array, but because the array doubles each time, those copies are rare enough that add is $O(1)$ averaged over all the calls.

The auxiliary space is the stack. The nodes on the stack all lie on one path down from the root, so the stack holds at most $h+1$ nodes, which is $O(h)$.

The iterators in the iterator chapter were $O(1)$ per call and used $O(1)$ auxiliary space. This one matches the time bound only when we amortize, and it does not meet the space bound. The $O(h)$ space is still reasonable. Our nodes have no link to their parent. So when the iterator stops partway through the traversal, it has to remember the ancestors it has not visited yet. It never keeps a copy of all $n$ values, the way the anti-pattern from the iterator chapter does when it gathers every value into a list first.