Iterator Problems
5 Iterator LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Keep only the state needed for the next value
An iterator separates traversal state from the collection it traverses. Its hasNext operation reports availability, while next produces the next element. For a binary search tree, a stack of the pending left spine gives an in-order sequence without first copying the entire tree into an array.
When to use it
Use a lazy iterator when the consumer may stop early or when materializing every value is expensive. PeekingIterator adds a one-element buffer; nested-list and run-length iterators need different state, but the same rule applies: repeated availability checks must not consume visible output.
Worked example
A BST has root 2, left child 1, and right child 3.
- Initialize the stack by descending left: push 2, then 1. The top is 1.
- Repeated hasNext calls return true without popping. next pops and returns 1.
- The following next pops 2 and pushes the left spine of its right subtree, here just 3. The final next returns 3.
The consumer receives 1, 2, 3 in order. Once the stack is empty, hasNext is false.
Time and space
For a tree of height h, initialization and auxiliary space are O(h). One next call can take O(h), but a full traversal pushes and pops each node once, so next is O(1) amortized over all n outputs.
Mistakes to check
- Do not use a valid value such as 0 or null as the only empty-buffer marker unless the input contract excludes it.
- A nested iterator must skip empty lists, including nested empty lists, before reporting that a next integer exists.
- Define exhausted-next behavior from the required interface. Also check whether mutation of the underlying collection is permitted during iteration.
Further reading: Java Iterator: hasNext and next contracts
Guide reviewed .