Iterators

What is this?

The lazy way to read a book is not to photocopy it first. An iterator's contract is that it produces the next element when asked and does no more work than that — which matters when the underlying structure is huge, expensive to materialise, or infinite.

Both problems here are traversals you already know, rewritten so they can be paused. Recursion cannot pause; an explicit stack can, because the stack is the paused state made visible.

💡 Fun fact: the flatten-a-nested-list iterator is where the difference between lazy and eager becomes concrete. Flattening the whole structure in the constructor is simpler to write and passes every test — and it defeats the purpose, because the caller may stop after one element or the nesting may be enormous. The lazy version pushes the list onto a stack in reverse so the first element ends up on top, and unwraps nested lists only when hasNext is forced to look.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: an explicit stack is a paused traversal. Do the unwrapping inside hasNext, keep hasNext free of side effects the caller can observe, and if the interface allows moving backwards, cache what you have already produced.

1. Lazy flattening

class NestedIterator:
    def __init__(self, nestedList):
        self.stack = list(reversed(nestedList))     # reversed → first element on top

    def hasNext(self):
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True                          # ready — do NOT pop
            self.stack.pop()                         # unwrap one level
            self.stack.extend(reversed(top.getList()))
        return False

    def next(self):
        return self.stack.pop().getInteger()         # hasNext guaranteed a value on top

Two design decisions carry this. Reversing on push means the leftmost element sits on top, preserving order. And the unwrapping loop lives in hasNext, not next — so next can assume an integer is waiting, and hasNext can be called repeatedly without disturbing anything, because it only ever pops lists, never the integer it reports.

2. The BST iterator, and going backwards

Forward iteration over a BST is the standard controlled inorder walk: push the entire left spine, and on each next pop a node and push the left spine of its right child. That yields one value per call in O(1) amortised, with O(h) memory rather than O(n).

Adding prev changes the design, because a stack cannot un-pop. The clean answer is a cache plus a pointer:

values:  [ 3, 7, 9, 15 ]      already produced
pointer:          ^           currently here

next():  if the pointer is not at the end of the cache, just move it right.
         otherwise, advance the real traversal, append to the cache, move right.
prev():  move the pointer left and read — never touches the traversal.

The live stack is only used when the caller moves past the frontier of what has been produced. Everything behind the frontier is answered from memory.

3. A 30-second worked example (lazy flatten)

[[1,1],2,[1,1]]:

init:      stack = [[1,1], 2, [1,1]]   reversed → top is the FIRST element
hasNext:   top is a list → pop, push its reversed contents
           stack = [[1,1], 2, 1, 1]    top is 1 → True
next:      → 1
next:      → 1
hasNext:   top is 2, an integer → True
next:      → 2
hasNext:   top is a list → unwrap → stack = [1, 1] → True
next:      → 1
next:      → 1
hasNext:   stack empty → False

The second nested list was not touched until the fourth next — which is the entire point. A caller that stopped after two elements would never have paid to unwrap it.

4. Where you'll actually meet this

• Database cursors. Rows are fetched in batches as the client pulls, not all at once.
• Paginated APIs. A client-side iterator that requests the next page only when the consumer exhausts the current one.
• Streaming parsers. SAX-style XML and JSON readers emit events lazily rather than building a full tree.
• Language runtimes. Python generators and Java's Iterator are this contract, and hasNext purity is part of it.
• File and directory walking. Recursive traversal exposed as a pull-based sequence over an enormous tree.

5. Problems in this chapter

▶ Flatten Nested List Iterator

Iterate the integers of an arbitrarily nested list. Stack pushed in reverse, unwrapping inside hasNext.
Pattern: lazy stack-driven flattening. Target: O(1) amortised per element, O(depth + width) space.

▶ Binary Search Tree Iterator II

Inorder iteration over a BST supporting next, prev, hasNext and hasPrev. A controlled stack walk plus a cache of produced values and a pointer into it.
Pattern: lazy traversal + cache for reverse movement. Target: O(1) amortised, O(h + produced) space.

6. Common pitfalls 🚫

• Flattening in the constructor. Correct output, wrong design, and the follow-up question exists to catch it.
• Pushing without reversing. The elements come out backwards — the single most common bug here.
• Consuming inside hasNext. It may be called any number of times before next; it must be idempotent from the caller's view.
• Doing the unwrapping in next. Then hasNext cannot honestly answer, and the two methods disagree about the state.
• Trying to make prev un-pop the stack. Stacks are one-directional; cache instead.
• Rebuilding the traversal on every prev. That is O(n) per call when the cache makes it O(1).
• Pushing the whole left subtree at construction. Push only the left spine — O(h), not O(n).

7. Key takeaways

1. An explicit stack is a paused recursion, which is exactly what an iterator needs.
2. Put the work in hasNext so next can assume a value is ready.
3. hasNext must be idempotent from the caller's perspective.
4. Push in reverse to preserve order through a stack.
5. Backwards movement means caching. The live traversal only runs past the frontier.
6. Left spine, not left subtree — O(h) memory is the whole advantage over materialising.
7. Why interviewers like it: the eager solution is trivially correct, so the question is really whether you understand what laziness buys and can honour the contract precisely.

Order: Flatten Nested List Iterator → Binary Search Tree Iterator II.