Same ranked catalog as Kth Smallest. Finance no longer wants rank k and a hang-up. They want a cursor: cheapest live SKU, then the next, then maybe stop after twenty of a million. The intern constructor dumped every inorder key into an ArrayList; next() bumped an index. A dozen SKUs was instant. A million-node catalog paid O(n) before the first next() and still held every key after the caller asked for three.

Keep the left spine on a stack; next() pops one visit and pushes that node’s right-child spine. Kth Smallest stops that same walk at visit k. Here you pause after each pop and resume on the next call. The BST post owns the invariant. The stack post owns the LIFO. Do not rebuild the traversal as a list.

The problem

Implement BSTIterator over the inorder of a BST. The constructor takes the root. next() returns the next smallest key. hasNext() is whether another key remains. The prompt treats next() as always valid when called. An empty tree is allowed at the board: the stack stays empty and hasNext() is false.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample tree. Inorder is 1, 3, 4, 6, 7, 8, 10, 14.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \
      4   7

next() × 3  →  1, then 3, then 4
hasNext() after 14  →  false
empty root          →  hasNext() false

Note: Inorder, not preorder. The first next() is the leftmost key, not the root.

Dump every inorder key in the constructor

Walk left, visit, right. Store every key, then next() indexes the list. Correct. Extra list. First next() waits for the whole tree.

class BSTIteratorDump {
    final List<Integer> inorder = new ArrayList<>();
    int index = 0;

    BSTIteratorDump(TreeNode root) {
        fill(root);
    }

    void fill(TreeNode node) {
        if (node == null) {
            return;
        }
        fill(node.left);
        inorder.add(node.val);
        fill(node.right);
    }

    int next() {
        return inorder.get(index++);
    }

    boolean hasNext() {
        return index < inorder.size();
    }
}

At a dozen nodes this is a rounding error. At a million-node catalog you still allocate n Integers before anyone asks for a key. The intended iterator never stores that list: the constructor only pushes the left spine.

Pause the left-spine walk on each next

Same ArrayDeque walk Kth Smallest used. Constructor: push root, then keep going left until null. next(): pop, that value is the visit, then push the popped node’s right child and that child’s left spine. hasNext() is whether the deque still holds a node. Deque and ArrayDeque, not java.util.Stack.

ctor: push 8, 3, 1
next: pop 1    no right     →  1
next: pop 3    push 6, 4    →  3
next: pop 4    no right     →  4
next: pop 6    push 7       →  6

The Java is that walk, split across constructor, next(), and hasNext().

class BSTIterator {
    final Deque<TreeNode> stack = new ArrayDeque<>();

    BSTIterator(TreeNode root) {
        pushLeft(root);
    }

    int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }

    boolean hasNext() {
        return !stack.isEmpty();
    }

    void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}

next() is amortized O(1) — each node is pushed once and popped once across the whole iteration, so n calls cost O(n). A single next() can walk a long right-then-left spine and is O(h) worst case. Space is O(h) for the deque, h being height, never the full n keys. Empty root: pushLeft is a no-op, hasNext() is false.

Note: Recursion that fills a list in the constructor is the dump again. The loop is the board answer unless they ask for Morris (mutate the tree for O(1) extra space).

What interviewers usually poke next

  • Why amortized, not every next? A skinny right-then-left chain can push h nodes in one call. Across all n visits the pushes still total n.
  • Kth Smallest. Same spine. They count pops and return on pop k. You leave the deque alive between calls. Do not flatten to a list to answer either question.
  • next() without hasNext(). The prompt says next() is valid when called. At the board, hasNext() false and an empty pop is the empty-tree case; do not invent a sentinel return unless they ask.
  • Why dump then index? It still works and pays O(n) extra memory up front. They asked for an iterator so the walk can stop early.

You are done with this problem when you can pop 1, then 3, then 4 on the drawing without having stored 14, and refuse to allocate an n-long list for a cursor that might stop at three.