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, but 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
hasNextis forced to look.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Short version: an explicit stack is a paused traversal. Do the unwrapping inside
hasNext, keephasNextfree 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 changing what the caller sees, 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 (a single call can push a whole spine, but each node is pushed and popped once overall), 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]] yields 1, 1, 2, 1, 1:
The second nested list was not touched until the hasNext call that precedes 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. Pull parsers (Java's StAX for XML, for example) hand back one event per call instead of building a full tree.
- Language runtimes. Java's
Iteratoris this contract, includinghasNextbeing safe to call repeatedly. Python generators give the same pull-one-at-a-time behaviour. - 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: next() O(1), hasNext() O(1) amortised, O(depth) extra space plus the siblings still pending along the current path.
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(h) constructor, O(1) amortised per call, O(h + k) space where k is the number of values produced so far.
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, and it is the most common bug here.
- Consuming inside
hasNext. It may be called any number of times beforenext; it must be idempotent from the caller's view. - Doing the unwrapping in
next. ThenhasNextcannot honestly answer, and the two methods disagree about the state. - Trying to make
prevun-pop the stack. Stacks are one-directional; cache instead. - Rebuilding the traversal on every
prev. That isO(n)per call when the cache makes itO(1). - Pushing the whole left subtree at construction. Push only the left spine:
O(h), notO(n).
7. Key takeaways
- An explicit stack is a paused recursion, which is exactly what an iterator needs.
- Put the work in
hasNextsonextcan assume a value is ready. hasNextmust be idempotent from the caller's perspective.- Push in reverse to preserve order through a stack.
- Backwards movement means caching. The live traversal only runs past the frontier.
- Left spine, not left subtree.
O(h)memory is the whole advantage over materialising. - 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.
Binary Search Tree Iterator II
Core idea: Keep the controlled in-order stack from the classic BST iterator to step forward lazily, but append every value it produces to a growing visited list and track a pointer into that list.
next()either re-reads a value you've already seen (if you stepped back) or advances the stack and records a new one.prev()never touches the tree: it slides the pointer back over the cache.
Problem, rephrased
You're building the scrollable cursor behind a database results pane: rows live in a sorted index (a BST), and the user can scroll both ways, so alongside FETCH NEXT the cursor must serve FETCH PRIOR. You're given the tree's root once, at construction. The cursor starts before the beginning, at a phantom slot smaller than every key, so the very first next() returns the minimum.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson