Iterator

The Problem It Solves

A BinarySearchTree holds its structure in private nodes. Letting clients traverse means either exposing root (encapsulation dead; anyone can rewire the tree) or writing inOrder(), preOrder(), byLevel() methods (traversal logic duplicated per consumer, and consumers can’t stream lazily). The Iterator pattern extracts traversal itself into an object with two questions — anything left? and what’s next? — letting any collection be consumed by uniform code without leaking structure.

 WITHOUT ITERATOR                      WITH ITERATOR

 tree.root → client walks nodes        for (X x : collection) { ... }
 internals exposed,                    client knows only hasNext()/next();
 traversal duplicated everywhere       structure stays private, lazy, swappable

The Contract

interface java.util.Iterator<E> {
    boolean hasNext();
    E next();                 // throws NoSuchElementException when exhausted
    default void remove() { throw new UnsupportedOperationException(); }
}
// Iterable<E> = "I can hand out iterators" → enables for-each syntax

Worked Example: In-Order BST Iterator

class BstInOrderIterator implements Iterator<Integer> {
    private final Deque<TreeNode> stack = new ArrayDeque<>();

    BstInOrderIterator(TreeNode root) {
        pushLeftSpine(root);                        // smallest element on top
    }
    private void pushLeftSpine(TreeNode n) {
        while (n != null) { stack.push(n); n = n.left; }
    }
    @Override public boolean hasNext() { return !stack.isEmpty(); }

    @Override public Integer next() {
        if (stack.isEmpty()) throw new NoSuchElementException();
        TreeNode node = stack.pop();
        pushLeftSpine(node.right);                  // prep successors lazily
        return node.value;
    }
}

class BinarySearchTree implements Iterable<Integer> {
    private TreeNode root;
    @Override public Iterator<Integer> iterator() {
        return new BstInOrderIterator(root);
    }
}

Properties worth stating in interviews: lazy — computes only consumed steps; memory O(h) where h = tree height (explicit stack), never O(n); multiple independent iterators over one tree coexist safely.

Fail-Fast: How ConcurrentModificationException Works

Collections track a modification counter (modCount). Each iterator snapshots it at creation and validates on every next():

 iter created (modCount=5) → list.add(x) (modCount=6)
 → next() detects 5 ≠ 6 → ConcurrentModificationException

Fail-fast is best-effort, not a correctness guarantee — detecting structural change early rather than allowing mysterious late corruption. For concurrent iteration use copy-on-write collections, snapshots, or explicit synchronization.

Design Decisions

Decision	Guidance
Snapshot vs live iteration	Live = no copies but sees/hates mutations; snapshot = stable but O(n) memory
remove() support	Only when the owning collection can delete mid-iteration consistently; else throw
Multiple cursors	State must live in the iterator, never the collection

Real-World Sightings

• Enhanced for-loop compiles to iterator calls — every Iterable type gets it free.
• Cursors in JDBC ResultSets, Kafka consumer iterators, database ORMs’ lazy result streams.
• Composite pattern relies on iterators for uniform tree walking.

Interview Framing

• “Implement in-order iterator with O(h) space” is a standard follow-up — the left-spine stack answer above is the target.