BST Iterator

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

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)

Store a stack representing the path to the next inorder node. Initialize by pushing the left spine from the root. Each Next() pops one node and then pushes the left spine of its right child.

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

• Invariant: the stack top is always the next smallest node.
• The stack stores the path to the next inorder node.
• Popping yields the next smallest, and pushing the right-left spine preserves order.
• Therefore successive Next() calls return values in ascending order.

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

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.