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()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 hasNexthasNext should do the work and nextnext should stay simple.
• Lazy flattening: unwrapping only as far as the next element requires.
• Wrapping an existing iterator to add peekpeek, and the one-element buffer that needs.
• Three real LeetCode problems solved in the browser: 173, 341, 284.

The cue

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:

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

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()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 nn 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:

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

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

The whilewhile loop handles arbitrary depth: [[[[1]]]][[[[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() == FalsehasNext() == False with no special case.

Pattern 3 — wrapping with a buffer

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

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()

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 hasNexthasNext in particular must report TrueTrue when the underlying iterator is exhausted but a buffered element remains.

The variant map

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()next() returning the next smallest number and hasNext()hasNext() reporting whether one remains. Aim for $O(1)$ average nextnext and $O(h)$ memory.

Constraints. 1 <= number of nodes <= 10^51 <= number of nodes <= 10^5, 0 <= Node.val <= 10^60 <= Node.val <= 10^6, and nextnext is only called when hasNexthasNext is true.

Examples. For [7,3,15,null,null,9,20][7,3,15,null,null,9,20]: next()next() gives 33, next()next() gives 77, hasNext()hasNext() gives TrueTrue, next()next() gives 99, next()next() gives 1515, hasNext()hasNext() gives TrueTrue, next()next() gives 2020, hasNext()hasNext() gives FalseFalse

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 NestedIntegerNestedInteger interface provides isInteger()isInteger(), getInteger()getInteger() and getList()getList().

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

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

LC 284 — Peeking Iterator · Medium

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

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

Examples. Over [1,2,3][1,2,3]: next()next() gives 11, peek()peek() gives 22, next()next() gives 22, next()next() gives 33, hasNext()hasNext() gives FalseFalse

LeetCode problem set

Interview follow-ups

Edge-case checklist

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

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()next().
• Put the work in hasNexthasNext 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 whilewhile 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.
• nextnext is $O(1)$ amortised, not worst case. Say which.
• To add peekpeek, buffer one element — and remember hasNexthasNext must count the buffer even when the source is exhausted.
• When the interface needs prevprev 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.