12. Iterators & Generators

Tutorial

A generator function (uses yield) is the easy way to produce a lazy sequence. The iterator protocol (__iter__ + __next__) is the manual version — you need it for LeetCode "Design Iterator" problems (BST Iterator, Peeking Iterator, Flatten Nested List Iterator), where the class must support repeated next()/hasNext() calls with saved state between them.

# ══ GENERATOR FUNCTIONS (yield) ════════════════════════════════
# Pauses and resumes — no full sequence built in memory
def inorder(node):
    if node:
        yield from inorder(node.left)
        yield node.val
        yield from inorder(node.right)

for val in inorder(root):     # pulls one value at a time
    print(val)

list(inorder(root))           # or collect them all

# ══ MANUAL ITERATOR PROTOCOL ═══════════════════════════════════
# Needed when the caller drives iteration with explicit next()/hasNext()
class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def __iter__(self):
        return self

    def __next__(self) -> int:
        if not self.stack:
            raise StopIteration
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

    def has_next(self) -> bool:
        return len(self.stack) > 0

it = BSTIterator(root)
while it.has_next():
    print(next(it))            # next() calls __next__ under the hood

Reference

Concept	Syntax	Notes
Generator function	def f(): yield x	Lazy; resumes where it left off
Delegate to sub-generator	yield from gen()	Common for recursive tree/graph traversal
Consume a generator	for x in gen(): / list(gen())
Iterator protocol	__iter__(self) returns self	Makes the object work in for loops
Advance manually	__next__(self)	Must raise StopIteration when exhausted
Manual advance call	next(it)	Invokes __next__; catches StopIteration in a for loop automatically
Generator expression	(x for x in it)	See §8 Comprehensions — built on the same protocol

---