BST Iterator

Implement an iterator over a Binary Search Tree (BST) that returns nodes in ascending order (inorder traversal).

Why this is worth learning

An iterator stores a suspended traversal, not a precomputed sorted array. Its stack is the frontier needed to produce exactly the next inorder value.

Before coding: one-minute experiment

Can one Next call take O(h) work even though Next is described as amortized O(1)?

Function signature

type BSTIterator struct { /* fields */ }

func Constructor(root *TreeNode) BSTIterator
func (it *BSTIterator) Next() int
func (it *BSTIterator) HasNext() bool

Inputs / outputs

• Constructor(root): initialize an iterator from the BST root.
• Next(): return the next smallest value.
• HasNext(): return true if a next value exists.

Example

    7
   / \
  3  15
     / \
    9  20

Calls: Next(), Next(), HasNext(), Next(), HasNext()
Returns: 3, 7, true, 9, true

Constraints

• 0 <= number of nodes <= 100_000
• Next() is only called if HasNext() is true

Core idea (near-solution)

A sorted slice would give simple Next calls but would traverse and store the entire tree before the first result. A lazy iterator instead preserves just the work recursion has postponed: the ancestors on the route to the next inorder node. Constructor pushes the left spine. Popping its top emits the next value; the popped node's right subtree contributes its own left spine. This produces the same sorted stream while retaining O(h) state. HasNext observes that state and must not change it; otherwise checking availability would consume an element.

Invariant: the stack top is always the next smallest node.

Algorithm (step-by-step)

1. Constructor: push all left children from root to the stack.
2. HasNext: return stack not empty.
3. Next:
   • Pop the top node.
   • Push the left spine of its right child.
   • Return the popped value.

Correctness sketch

After construction, pushing the root's left spine puts the smallest node at the stack top. Before each Next, that top is the smallest unvisited node. Pop it and push the left spine of its right subtree; those nodes are the next candidates after the popped value, while older ancestors remain below them. This restores the frontier invariant. HasNext is true exactly when a candidate remains on the stack. Each tree node is pushed once and popped once over a full traversal, giving linear total work despite occasional Next calls pushing several nodes. Independent iterator instances retain independent frontiers.

Trace (hand walkthrough)

Example input:
    7
   / \
  3  15
     / \
    9  20

Calls: Next(), Next(), HasNext(), Next(), HasNext()
Returns: 3, 7, true, 9, true

Walk:
- init stack with left spine: [7,3] (top=3)
- Next()->3; stack=[7]
- Next()->7; push left spine of 15 -> stack=[15,9]
- HasNext()->true; Next()->9; HasNext()->true

Pitfalls to avoid

• Forgetting to push the left spine of node.Right in Next().
• Pushing the entire subtree (should only push the left spine).
• Returning values without checking HasNext() (assume caller follows contract).

Debugging lens

Interleave two iterators over the same tree, repeat HasNext without consuming values, and exhaust an empty iterator without calling Next. The tree must remain unchanged.

Complexity

• Constructor: O(h) time, O(h) space.
• Each Next: amortized O(1) time, O(h) space total.

Implementation notes (Go)

• Use a []*TreeNode slice as a stack and a helper pushLeft(node).
• Handle root == nil by leaving the stack empty.

Reconstruction checkpoint

An iterator has pending stack [10,3] bottom-to-top, and node 3 has right subtree rooted at 8 with left child 5. After Next, what value and stack result? What can two consecutive HasNext calls change?

Return to Binary Search Tree · Module quiz