Nested Iterators And Lazy Stack Traversal

What's being tested

Implementing a nested-list iterator tests lazy traversal using an explicit stack (not recursion), correct hasNext()/next() state management, and per-operation complexity reasoning. Interviewers look for clean iterator semantics, amortized cost analysis, and edge-case handling (empty lists, deep nesting).

Patterns & templates

• Lazy DFS with a stack of iterators or (list, index) pairs — advance in hasNext() until you expose an integer to return.

• Push children when you see a nested list: push its iterator/index on the stack; pop when an iterator is exhausted.

• Flatten-on-demand vs preflatten — preflattening is simple (O(n) time/space), lazy gives O(d) stack space and better streaming behavior.

• Use a peek-style advance inside hasNext() so next() is a cheap pop; keep hasNext() idempotent and side-effecting only to prepare state.

• Aim for amortized O(1) per next() (each element visited once) and O(depth) stack space, where depth is maximal nesting.

• Common implementation forms: stack of Iterator<Nested> objects, stack of (list, idx) tuples, or stack of flattened buffers per node for language constraints.

Common pitfalls

Pitfall: Implementing hasNext() without advancing past empty nested lists causes infinite loops or repeated false negatives.

Pitfall: Preflattening every nested list uses O(n) memory and loses streaming semantics when input can be large or unbounded.

Pitfall: Mutating the input structure or relying on recursion risks stack overflow for deep nesting; prefer an explicit stack for robustness.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.