Iterator pattern - Low-Level Design Guide

Overview

The Iterator pattern provides a way to access elements of a collection sequentially without exposing its internal structure. Whether the data is an array, a linked list, a tree, or a paginated API, clients use the same hasNext()/next() (or for...of) interface.

Iterators decouple traversal from storage, allow multiple traversal strategies (in-order, level-order, filtered), support lazy evaluation of large or infinite sequences, and let several traversals run at once. Most languages build them in: Java's Iterable, JavaScript's Symbol.iterator and generators, Python's __iter__.

A TV remote's channel button

You press 'next channel' without knowing how channels are stored or numbered internally. The remote remembers where you are and moves to the next one.

When to use it

Custom collections should work with for-each loops.
Different traversal orders over the same structure.
Lazy iteration over large or remote data (pagination, streams).

Where it shows up in interviews

Custom traversal

Recognize it when: iterate a tree, graph, or composite.

Design a file system iterator
BST iterator (LeetCode 173)

Lazy pagination

Recognize it when: iterate results from an API page by page.

Design an SDK list method
Design a playlist shuffle iterator

Where it is used in real software

Java Iterable and Streams

for-each loops and streams work on any Iterable.

JavaScript generators

function* and async iterators power lazy sequences and paginated SDKs (for await ... of).

Cloud SDK paginators

AWS SDK v3 paginators iterate across pages transparently.

Key terms

Iterator: Object tracking position with next()/hasNext().
Iterable / aggregate: Collection that creates iterators.
External vs internal iteration: Client drives next() vs collection calls a callback (forEach).
Fail-fast iterator: Throws if the collection changes during iteration.
Generator: Function that yields values lazily.

How it works, step by step

1
Decide the traversal order
In-order, BFS, filtered.
2
Store traversal state in the iterator
Stack, index, cursor.
3
Implement next and hasNext
Or a generator.
4
Make the collection iterable
Return a new iterator each time.
5
Handle concurrent modification
Fail fast or iterate a snapshot.

BST in-order iterator with a stack

Tree: 7 (3, 15 (9, 20))

Call	Stack after	Returns
init	[7, 3]	-
next()	[7]	3
next()	[15, 9]	7
next()	[15]	9
next()	[20]	15
next()	[]	20

NOWCall: init | Stack after: [7, 3] | Returns: -

O(h) memory and amortized O(1) per next(), without flattening the tree.

Implementation

1type TreeNode = { val: number; left?: TreeNode; right?: TreeNode };2 3class BST implements Iterable<number> {4  constructor(private root?: TreeNode) {}5 6  *[Symbol.iterator](): Iterator<number> {7    const stack: TreeNode[] = [];8    let node = this.root;9    while (node || stack.length) {10      while (node) { stack.push(node); node = node.left; }11      node = stack.pop()!;12      yield node.val;13      node = node.right;14    }15  }16}17 18const tree = new BST({ val: 7, left: { val: 3 }, right: { val: 15, left: { val: 9 }, right: { val: 20 } } });19console.log([...tree]); // [3, 7, 9, 15, 20]20 21// Lazy pagination across an API22async function* allOrders(fetchPage: (cursor?: string) => Promise<{ items: string[]; next?: string }>) {23  let cursor: string | undefined;24  do {25    const page = await fetchPage(cursor);26    yield* page.items;27    cursor = page.next;28  } while (cursor);29}

Complexity and performance

BST iterator next()Amortized O(1)

O(h) memory.

Generator overheadSmall per yield

Lazy evaluation.

Trade-offs

Lazy vs eager

Lazy iteration saves memory but holds resources (cursors, connections) until finished.

Modification during iteration

Fail-fast iterators detect bugs; snapshot iterators are safe but cost a copy.

Variants and related techniques

Internal iteration

forEach(callback) where the collection drives the loop.

Cursor-based iteration

Database cursors and API page tokens.

Common mistakes

Modifying the collection in a for-each loop.
Fix: Use iterator.remove() or collect changes first.
Reusing one iterator for multiple loops.
Fix: Return a fresh iterator per call.

Interview questions

How would you iterate a BST in order with O(h) memory?

Keep a stack: push all left children from the root; next() pops a node, then pushes the left spine of its right child. Each node is pushed and popped once, giving amortized O(1) per call.

Why use an iterator instead of returning a list?

It hides the internal structure, supports lazy evaluation of large or infinite sequences, and allows different traversal orders without copying data.

Practice problems

Problem	Difficulty	What it trains
Iterator over a nested list (flatten)	Medium	Stack-based traversal.
Round-robin iterator over multiple lists	Medium	Interleaving.