Design Iterators and Flatteners

An iterator turns a traversal inside out. Instead of a recursion that runs to completion and hands back a list, you must pause after every element and resume when asked. The state that recursion kept implicitly on the call stack now has to live in your object, explicitly.

That inversion is the whole skill:

Take the recursion, replace the call stack with an explicit stack you own, and expose one step of it as next().

The second theme is laziness. Flattening everything up front is usually allowed and often simpler — but it costs $O(n)$ memory and does work the caller may never need. Interviewers ask for the lazy version because it is the one that works on a stream, or on a structure too large to materialise.

What you’ll learn

• Converting an in-order recursion into an explicit-stack iterator.
• Why hasNext should do the work and next should stay simple.
• Lazy flattening: unwrapping only as far as the next element requires.
• Wrapping an existing iterator to add peek, and the one-element buffer that needs.
• Three real LeetCode problems solved in the browser: 173, 341, 284.

The cue

You are looking at an iterator design when…

• The interface is next() and hasNext() — 173, 341, 284, 900.
• You must flatten a nested or 2D structure on demand — 341, 251, 281.
• The problem says ”$O(1)$ average next” and ”$O(h)$ memory” — that pairing rules out pre-flattening and demands the lazy design.
• You must add a capability to an iterator you cannot modify — 284 peek.
• A traversal must be interleaved with other work, so it cannot run to completion.

The hasNext / next contract

Two rules make these designs clean:

1. hasNext() must be idempotent. Calling it twice in a row, with no next() between, must give the same answer and must not consume anything. Test harnesses call it repeatedly.
2. Put the work in hasNext. Let it advance internal state until either a real element is ready or the source is exhausted. Then next() is a trivial “return the ready element”. The reverse split — work in next, prediction in hasNext — forces you to look ahead twice and duplicate logic.

For LC 341 this is load-bearing: hasNext is where the lazy unwrapping happens.

Visual intuition

A BST iterator (LC 173) is an in-order traversal paused between steps. The stack in this trace is exactly the iterator’s state — everything it must remember to resume:

treeAn iterator is a traversal you can stop in the middle ofLC 173 · O(1) amortised next()

call stack

7

1def inorder(node, out):2    if node is None:3        return4    inorder(node.left, out)5    out.append(node.val)      # visit6    inorder(node.right, out)

node7stack depth1

enterEnter 7. The recursive call is pushed onto the stack, which is now 1 frame deep.

Play‹›1/16⟲

Read the call stack as the object's fields rather than as recursion. next() = pop, visit, then push the left spine of the right child; hasNext() = 'is the stack non-empty'. The traversal is O(n) overall and the stack never exceeds the tree's height, which is where the O(h) space and O(1) amortised next() both come from.

Pattern 1 — recursion to explicit stack

The BST in-order walk descends left, visits, then goes right. As an iterator, the “descend left” part becomes a helper and the stack holds the ancestors still owed a visit:

bst_iterator.py

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)          # prime it with the leftmost spine
 
    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left
 
    def next(self):
        node = self.stack.pop()        # the next smallest
        self._push_left(node.right)    # its right subtree comes after it
        return node.val
 
    def hasNext(self):
        return len(self.stack) > 0

Space $O(h)$, not $O(n)$ — the stack only ever holds one root-to-node path. That is precisely what the problem asks for, and it is why pre-flattening the whole tree into a list (also valid, and $O(n)$ space) is the answer they want you to improve on.

next() is $O(1)$ amortised: a single call may push a whole left spine, but each node is pushed once and popped once across the full traversal, so n calls cost $O(n)$ total. That is the same accounting as the two-stack queue.

Pattern 2 — lazy flattening

LC 341 gives a nested list where each element is either an integer or another nested list, arbitrarily deep. The lazy design keeps a stack of unprocessed items and unwraps only when asked:

nested_iterator.py

class NestedIterator:
    def __init__(self, nestedList):
        self.stack = list(reversed(nestedList))   # reversed so pop() takes the front
 
    def next(self):
        return self.stack.pop().getInteger()      # hasNext guaranteed it is an int
 
    def hasNext(self):
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True                       # ready -- do NOT consume it
            self.stack.pop()                      # unwrap ONE level
            self.stack.extend(reversed(top.getList()))
        return False

Two details, both easy to get wrong

Reverse when pushing. A stack pops from the end, but you must yield the list front first. Pushing reversed(items) makes the first item end up on top. Forgetting this silently reverses the output.

hasNext must not consume the integer it found. It returns True while leaving the element on the stack for next() to take. Popping it there means next() has nothing to return, and two hasNext calls in a row would skip an element.

The while loop handles arbitrary depth: [[[[1]]]] unwraps one level per iteration until an integer surfaces. And empty lists are skipped naturally — they push nothing, so the loop simply continues. That is why [[]] correctly reports hasNext() == False with no special case.

Pattern 3 — wrapping with a buffer

LC 284 asks you to add peek() to an iterator that only offers next() and hasNext(). Since you cannot un-consume an element, you buffer one:

peeking_iterator.py

class PeekingIterator:
    def __init__(self, iterator):
        self.it = iterator
        self.buffer = None                     # the one element we pulled early
 
    def peek(self):
        if self.buffer is None:
            self.buffer = self.it.next()       # pull and hold
        return self.buffer
 
    def next(self):
        if self.buffer is not None:
            value, self.buffer = self.buffer, None
            return value
        return self.it.next()
 
    def hasNext(self):
        return self.buffer is not None or self.it.hasNext()

Every method must now consider both states — buffer filled or empty — and hasNext in particular must report True when the underlying iterator is exhausted but a buffered element remains.

Using None as “empty” is a real limitation

If the stream could legitimately contain None, this breaks. The robust version uses a separate self.has_buffer = False boolean, or a unique sentinel object. LC 284’s values are integers so None is safe, but flagging the assumption is exactly the kind of thing that distinguishes a careful answer.

Dry run

The BST iterator, counting pushes

The LC 173 tree, height 3, five nodes:

text

      7
    /   \
   3     15
        /  \
       9    20

__init__ primes the leftmost spine, then five next() calls drain it. The pushed column is the work each call does; the stack column is the space it holds.

Call	Returns	Pushed this call	Stack after
__init__	—	2	[7, 3]
next()	3	0	[7]
next()	7	2	[15, 9]
next()	9	0	[15]
next()	15	1	[20]
next()	20	0	[]
hasNext()	False	—	[]

Two claims the trace settles:

• Space is $O(h)$, not $O(n)$. The stack never exceeds 2 entries, against $h = 3$ and $n = 5$. It only ever holds a partial root-to-node path — ancestors still owed a visit — which is why this design beats pre-flattening the tree into a list. That alternative is correct and $O(n)$ space, and it is exactly the answer the problem is asking you to improve on.
• next() is $O(1)$ amortised, not worst case. Three calls pushed nothing; one pushed two nodes. Total pushes across the whole traversal: 5, one per node. Each node is pushed once and popped once, so n calls cost $O(n)$ — the same accounting as the two-stack queue, and the same phrasing to use out loud.

The values come out 3, 7, 9, 15, 20 — sorted, because in-order on a BST is sorted. That is the property the iterator interface is hiding, and worth naming.

Lazy flattening, one unwrap at a time

[[1, 1], 2, [1, 1]]. The stack is written top on the right, so the rightmost element is what pop() takes next.

Step	Unwraps in hasNext	Stack when hasNext returns	next()	Stack after
init	—	[[1,1], 2, [1,1]]	—	—
1	1	[[1,1], 2, 1, 1]	1	[[1,1], 2, 1]
2	0	[[1,1], 2, 1]	1	[[1,1], 2]
3	0	[[1,1], 2]	2	[[1,1]]
4	1	[1, 1]	1	[1]
5	0	[1]	1	[]
6	0	[] -> False	—	[]

Output [1, 1, 2, 1, 1]. Notice the input was reversed on construction — the initial stack reads [[1,1], 2, [1,1]] with the first sublist at the bottom — and that nothing is unwrapped until someone asks. Step 3 does zero work; step 4 does one unwrap because the top is finally a list again.

hasNext leaves the integer in place. At step 1 it returns True with 1 still on the stack, and next() takes it. Pop it inside hasNext and next() has nothing to return — and worse, two hasNext calls in a row would silently drop an element. This is why hasNext here is the method doing all the work while next() is a one-liner: the inspection has to be non-destructive.

Depth and the empty cases, same code, no special handling:

Input	Unwraps before the first value	Output
[1, [4, [6]]]	0, then 1, then 1	[1, 4, 6]
[[[[1]]]]	3 in a single hasNext call	[1]
[[]]	1, then the stack is empty	[] — hasNext() is False
[[], [], [3]]	3 in a single call	[3]

[[[[1]]]] is why hasNext is a while and not an if: four levels collapse in one call. [[]] and [[], [], [3]] are why empty lists need no special case — unwrapping one pushes nothing, so the loop just goes round again. Getting hasNext() == False for [[]] for free is a good sign the structure is right.

The peeking wrapper, both states

[1, 2, 3] underneath. The last two columns are what the wrapper is actually managing — its own buffer versus how far the underlying iterator has been advanced.

Call	Returns	buffer	Underlying position
next()	1	None	1
peek()	2	2	2
next()	2	None	2
next()	3	None	3
hasNext()	False	None	3

Row 2 is the whole trick: peek() advanced the underlying iterator to position 2 while returning a value the caller has not consumed. Row 3 then returns that buffered 2 without touching the underlying iterator — its position stays at 2. The wrapper is one element ahead of the caller from that point on, and every method has to account for it.

That includes hasNext: if the underlying iterator is exhausted but the buffer is full, the answer is still True. Check only the underlying iterator and peek() at the last element makes the sequence appear to end one value early.

Using None as the empty marker is the assumption to flag out loud. LC 284’s values are integers, so it is safe here; a stream that can legitimately contain None needs a separate has_buffer boolean or a unique sentinel object.

Bulk consumption: LC 900

RLEIterator([3, 8, 0, 9, 2, 5]) — three 8s, zero 9s, two 5s. n(k) consumes k values and returns the last one.

Call	Encoding after	i	Returns
n(2)	[1, 8, 0, 9, 2, 5]	0	8
n(1)	[0, 8, 0, 9, 2, 5]	0	8
n(1)	[0, 8, 0, 9, 1, 5]	4	5
n(2)	[0, 8, 0, 9, 0, 5]	6	-1

Row 3 crosses two run boundaries in one call: the 8-run is exhausted, the 9-run has count zero and is skipped entirely, and the value comes from the 5-run. That is why the body is a loop — one request can span any number of runs, and a zero-count run must be stepped over rather than special-cased.

Row 4 runs off the end. Only one value remained and two were asked for, so the correct answer is -1 — not the last value seen, and not an exception. Note the counts are decremented in place, so the state is the encoding array plus one index; nothing else is needed to survive a partially-consumed run.

Complexity

Design	next	Space
Pre-flatten to a list	$O(1)$	$O(n)$
BST iterator (stack)	$O(1)$ amortised	$O(h)$
Lazy nested iterator	$O(1)$ amortised	$O(\text{depth} + \text{breadth})$
Peeking wrapper	$O(1)$	$O(1)$

The variant map

Variant	The state you keep	Canonical problem
In-order tree iteration	Stack of the left spine	173
Nested list flattening	Stack of unprocessed items, reversed	341
Add peek	A one-element buffer	284
2D flattening	Row and column indices	251 (Premium)
Run-length decoding	Index + remaining count in the current run	900
Zigzag / interleaved iteration	A queue of sub-iterators	281 (Premium)

LC 900 is the state-machine version

RLE Iterator takes [count, value, count, value, ...] and must serve n(k) — “consume k values and return the last one”. The state is an index into the encoding plus how much of the current run remains.

The subtlety is that a single call may span several runs, so you loop: subtract from the current run, and when it is exhausted, advance to the next. And if you run out of encoding mid-request you must return -1.

It is a good reminder that “iterator” does not always mean one element at a time — the interface may consume in bulk, and the state has to survive partially-consumed runs.

Practice — real LeetCode problems

LC 173 — Binary Search Tree Iterator · Medium

Problem. Implement an iterator over the in-order traversal of a BST, with next() returning the next smallest number and hasNext() reporting whether one remains. Aim for $O(1)$ average next and $O(h)$ memory.

Constraints. 1 <= number of nodes <= 10^5, 0 <= Node.val <= 10^6, and next is only called when hasNext is true.

Examples. For [7,3,15,null,null,9,20]: next() gives 3, next() gives 7, hasNext() gives True, next() gives 9, next() gives 15, hasNext() gives True, next() gives 20, hasNext() gives False

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

This is the iterative in-order traversal from BST Patterns, with its loop body exposed as next(). The stack holds exactly the ancestors whose values have not yet been emitted.

Time $O(1)$ amortised per next — each node is pushed once and popped once, so n calls cost $O(n)$ in total. A single call can be $O(h)$ when it pushes a long spine. Space $O(h)$.

Start by naming the simple solution: flatten the whole tree into a list in the constructor and serve from an index. It is $O(1)$ worst-case next and perfectly correct — but $O(n)$ space, which is what the stated $O(h)$ memory target rules out. Offering it first and then improving reads well.

The invariant to state: the stack contains the path of nodes whose left subtrees are fully consumed but which have not themselves been visited. Popping one yields the smallest remaining; pushing its right child’s left spine restores the invariant.

Follow-ups you should expect:

• “Add prev() for a bidirectional iterator (LC 1586)?” The single stack no longer suffices, since it has forgotten what it popped. Either keep a second stack of visited nodes, or fall back to pre-flattening with an index — and here that trade is genuinely worth it.
• “What if the tree is modified during iteration?” Classic invalidation problem; you would need version counters or a snapshot.
• “Iterate in reverse order?” Mirror it — push the right spine and descend left in next.
• ”$O(1)$ worst case for next?” Not with $O(h)$ space; you would need threaded trees or Morris traversal, which mutates the tree.

LC 341 — Flatten Nested List Iterator · Medium

Problem. You are given a nested list of integers, where each element is either an integer or a list whose elements may also be integers or lists. Implement an iterator that flattens it. The NestedInteger interface provides isInteger(), getInteger() and getList().

Constraints. 1 <= nestedList.length <= 500, integer values in [-10^6, 10^6].

Examples. [[1,1],2,[1,1]] flattens to [1,1,2,1,1] · [1,[4,[6]]] flattens to [1,4,6] · [[]] flattens to []

About the harness in this exercise

LeetCode supplies NestedInteger as a built-in class. The editor below defines a minimal stand-in with the same three methods, plus a wrap() helper that converts ordinary Python lists into it — so you can implement and test the real interface locally.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Keep a stack of items not yet emitted. hasNext unwraps lists lazily until an integer sits on top; next then simply takes it.

Time $O(1)$ amortised per next — each NestedInteger is pushed and popped at most once across the whole traversal. Space $O(\text{total items})$ worst case, but only $O(\text{depth} + \text{breadth along the current frontier})$ in practice, versus $O(n)$ for eager flattening.

Three things carry the correctness:

• reversed on every push. Stacks are LIFO but iteration is front-to-back.
• hasNext does not consume. It returns True with the integer still on the stack. Two consecutive hasNext calls must be safe.
• The while loop, not an if. [1,[4,[6]]] needs two unwraps to reach 6, and [[]] needs one unwrap that yields nothing at all. A single if handles neither.

[[]] returning [] and [[], [1]] returning [1] are the empty-list cases, and they work with no special handling: unwrapping an empty list pushes nothing, the loop continues, and the stack either empties or reveals the next item.

The eager alternative — recursively flatten everything in the constructor into a plain list — is much shorter and perfectly acceptable if the interviewer allows it. Say it, then explain that lazy evaluation avoids $O(n)$ upfront memory and work the caller may never ask for.

Follow-ups you should expect: “Do it eagerly instead” — have the 3-line recursive flatten ready. “What if the structure were infinite or streamed?” — laziness becomes mandatory; eager flattening cannot terminate. “Add peek?” — compose with the LC 284 buffer. “Flatten a 2D vector (LC 251)?” — simpler: two indices, advancing past empty rows.

LC 284 — Peeking Iterator · Medium

Problem. Given an iterator supporting next() and hasNext(), design a wrapper that also supports peek() — returning the next element without advancing.

Constraints. 1 <= nums.length <= 1000, all calls valid.

Examples. Over [1,2,3]: next() gives 1, peek() gives 2, next() gives 2, next() gives 3, hasNext() gives False

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

You cannot rewind an iterator, so peek must consume from the source and stash the result. Every method then has to account for the buffer.

Time $O(1)$ for all three. Space $O(1)$.

The case that catches people is the second half of the test: after PeekingIterator(Iterator([7])) and one peek(), the underlying iterator is exhausted, yet the wrapper still has an element to serve. So hasNext() must be buffer is not None or self.it.hasNext() — delegating straight through returns False and loses an element.

peek() twice in a row returning the same value is also part of the contract, which the buffered design gives for free.

The None sentinel is an assumption

Using None for “buffer empty” fails if the stream can contain None. Here the values are integers, so it is safe — but the robust version keeps a separate self.has_buffer boolean, or a module-level unique sentinel:

python

_EMPTY = object()

Raising this unprompted is a cheap way to show you think about interface robustness rather than just passing the given tests.

Follow-ups you should expect: “Peek k elements ahead?” — buffer a deque of up to k pulled elements. “Add prev?” — you must retain history, so keep a list of everything emitted. “Wrap a Python generator?” — the same design; itertools.chain([peeked], gen) is another idiomatic route worth mentioning. “What if next on the source can raise instead of returning?” — catch it in peek and record exhaustion.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 1586 is where laziness stops paying

BST Iterator II adds prev(). The single stack cannot help: it has already discarded the nodes it popped.

Options are to maintain a second stack of visited nodes, or simply to pre-flatten the tree into a list and keep an index — which makes next, prev and both hasNext/hasPrev trivially $O(1)$ at $O(n)$ space.

That is a genuinely useful lesson: laziness is a means, not a goal. When the interface needs random or backwards access, materialising the sequence is the better engineering choice, and saying so deliberately is stronger than defending the clever design past its usefulness.

6 problems

0 easy6 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○173Binary Search Tree IteratormediumStack of the left spine -- $O(h)$ memory, not $O(n)$LeetCode Top Interview 150
• ○251Flatten 2D VectorpremiummediumTwo indices, skipping empty rows
• ○284Peeking IteratormediumOne-element buffer; `hasNext` must count it
• ○341Flatten Nested List IteratormediumLazy unwrapping in `hasNext`; push reversed
• ○900RLE IteratormediumBulk consumption spanning several runs; return `-1` when exhausted
• ○1586Binary Search Tree Iterator IIpremiummediumAdd `prev()` -- one stack is no longer enough

Interview follow-ups

They ask	What they’re checking	The answer
“Why not pre-flatten?”	Trade-off awareness	It works and is simpler, but costs $O(n)$ memory and does work the caller may not need
“Complexity of next?”	Precision	$O(1)$ amortised; a single call can be $O(h)$ while pushing a spine
“Is hasNext idempotent?”	The contract	It must be — it may advance internal state but must not consume the element it reports
“Where should the work live?”	Design judgement	In hasNext, so next is a trivial hand-off and the lookahead logic exists once
“Why push reversed?”	Attention to detail	A stack pops from the end but iteration must yield the front first
“What if values can be None?”	Robustness	The None-as-empty sentinel breaks; use a boolean flag or a unique sentinel
“Add prev?”	Knowing when to change design	History is needed — second stack, or pre-flatten and index

Edge-case checklist

• Empty source — hasNext() must be False immediately and not raise.
• Deeply nested empty lists — [[]], [[[]]]; must flatten to nothing.
• Empty list among real values — [[], [1]]; skipped without consuming.
• Arbitrary nesting depth — [1,[4,[6]]]; needs a while, not an if.
• hasNext called repeatedly — must be idempotent.
• peek called repeatedly — must return the same value each time.
• peek at the last element — source exhausted but the buffer holds a value; hasNext must still be True.
• next immediately after peek — must return the buffered element, not skip it.
• Single-node tree / single-element source — the smallest case for every design.

Self-check

pch.quizTag pch.quizDefaultTitle

1. Why is the BST iterator's space O(h) rather than O(n)?

   A Because the tree is balanced, so h is log n B The stack only ever holds a partial root-to-node path -- the ancestors still owed a visit C Because `next()` deletes nodes as it visits them D It is O(n); the O(h) claim only holds for the recursive version
   pch.quizShowAnswer

   B — The stack only ever holds a partial root-to-node path -- the ancestors still owed a visit — At any moment the stack is one descending-left path, never the whole tree. In the five-node trace it never exceeded two entries. The O(h) bound holds for a degenerate tree too -- it is just that h = n there. Pre-flattening the tree into a list is also correct and also passes, at O(n) space; the O(h) design is exactly the improvement the problem is asking for.

2. The BST iterator's `next()` is described as O(1) amortised. Which observation justifies that?

   A The stack is always small, so each call is fast in practice B Each node is pushed once and popped once across the whole traversal, so n calls do O(n) total work C The left spine is precomputed in the constructor D `_push_left` is O(1) because it only follows left pointers
   pch.quizShowAnswer

   B — Each node is pushed once and popped once across the whole traversal, so n calls do O(n) total work — One call can push a whole left spine -- in the trace, `next()` returning 7 pushed two nodes while three other calls pushed none. Total pushes across the traversal: exactly n, one per node. That is the amortisation argument, and it is the same accounting as the two-stack queue: the push pre-pays for the pop.

3. `NestedIterator.__init__` does `list(reversed(nestedList))`. What breaks without the reverse?

   A Nothing -- the stack order is arbitrary B The output comes out reversed, because a stack pops from the end but the list front must be yielded first C Deeply nested lists cause infinite recursion D `hasNext` starts returning True on empty input
   pch.quizShowAnswer

   B — The output comes out reversed, because a stack pops from the end but the list front must be yielded first — You need the first element on *top*, and a stack's top is its end. Push in reverse and the front lands on top. Skip the reverse and every level comes out backwards -- a silent failure with no crash, on a structure that still looks well-formed. The same reverse is needed inside `hasNext` when a sublist is unwrapped.

4. Why must `hasNext` return True without popping the integer it found?

   A Popping would be O(n) B `next()` needs that element to return, and two `hasNext` calls in a row would otherwise skip a value C The integer must stay for `peek()` to work D It does not matter; `next()` can re-unwrap
   pch.quizShowAnswer

   B — `next()` needs that element to return, and two `hasNext` calls in a row would otherwise skip a value — `hasNext` is an inspection, so it has to be non-destructive. The unwrapping it does is safe -- unwrapping a list changes representation, not content -- but consuming the integer removes a value nobody asked for. That is why in this design `hasNext` carries all the logic and `next()` is a one-liner.

5. For input `[[]]`, `hasNext()` returns False with no special case for empty lists. Why?

   A The constructor filters empty lists out B Unwrapping an empty list pushes nothing, so the `while` loop simply continues and finds an empty stack C `isInteger()` returns False for empty lists, which ends the loop D It is a lucky accident that fails on `[[], [], [3]]`
   pch.quizShowAnswer

   B — Unwrapping an empty list pushes nothing, so the `while` loop simply continues and finds an empty stack — The loop pops the empty list, extends by nothing, and goes round again -- exactly the behaviour you would have written a special case for. `[[], [], [3]]` works the same way: three unwraps in a single hasNext call, then 3 surfaces. Same reason `[[[[1]]]]` works: the `while` collapses four levels in one call, which is why it is a while and not an if.

6. In `PeekingIterator`, why must `hasNext` check the buffer as well as the underlying iterator?

   A To avoid a double-advance of the underlying iterator B A `peek()` at the last element leaves the underlying iterator exhausted while a value is still pending C Because the buffer may contain None D It does not need to; the underlying `hasNext` is sufficient
   pch.quizShowAnswer

   B — A `peek()` at the last element leaves the underlying iterator exhausted while a value is still pending — After `peek()` the wrapper is one element ahead of the caller. Peek the final value and the underlying iterator reports empty even though the caller has not received it -- so checking only the underlying iterator makes the sequence appear to end one value early. Every method on a buffering wrapper has to consider both states.

Recall card

• An iterator is a paused traversal. Write the recursion, then ask what the call stack was holding — that state, made explicit, is the iterator.
• BST iterator = stack of the left spine. next() pops, then pushes the popped node’s right spine. $O(h)$ space, $O(1)$ amortised — each node pushed once, popped once.
• Pre-flattening to a list is correct and $O(n)$ space. It is the answer the $O(h)$ design exists to beat; say so before you write the better one.
• Lazy flattening = stack of unprocessed items, pushed reversed so the front is on top. Forget the reverse and the output silently reverses.
• hasNext unwraps but never consumes. Unwrapping changes representation; popping the integer loses a value and makes two hasNext calls in a row skip one.
• Use while, not if, when unwrapping — [[[[1]]]] collapses four levels in one call, and empty lists then need no special case at all.
• peek() = a one-element buffer. Every method must handle both states, and hasNext must return True when the underlying iterator is exhausted but the buffer is full.
• None as “buffer empty” is an assumption — fine for integer streams, otherwise use a boolean or a sentinel. Flagging it is what makes the answer careful.
• Bulk interfaces exist (LC 900): the state must survive a partially consumed run, one call can span several runs, and running off the end returns -1.

Recap

• An iterator is a paused traversal: replace the recursion’s call stack with an explicit stack you control, and expose one step as next().
• Put the work in hasNext and keep it idempotent — it may advance internal state but must never consume the element it reports.
• Lazy flattening: a stack of unprocessed items, pushed reversed, unwrapped one level at a time in a while loop. Empty lists then need no special case.
• The BST iterator’s stack is $O(h)$, not $O(n)$ — that memory bound is precisely what the problem is asking you to achieve over pre-flattening.
• next is $O(1)$ amortised, not worst case. Say which.
• To add peek, buffer one element — and remember hasNext must count the buffer even when the source is exhausted.
• When the interface needs prev or random access, pre-flattening becomes the better design. Laziness is a means, not an end.

Next: Design with Randomization — $O(1)$ random selection, weighted picks, and unbiased shuffles.