Binary Search Tree Iterator — LeetCode 173 Stack-Based Inorder

Problem Statement#

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• BSTIterator(TreeNode root) initializes the iterator.
• int next() returns the next number in the in-order traversal.
• boolean hasNext() returns true if there is still a number to return.

You may assume next() is always called when hasNext() is true.

Constraints:

• The number of nodes in the tree is in the range [1, 10^5]
• 0 <= Node.val <= 10^6
• At most 10^5 calls will be made to hasNext and next

Input:  ["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"]
        [[[7,3,15,null,null,9,20]],[],[],[],[],[],[],[],[],[]]
Output: [null,3,7,true,9,true,15,true,20,false]

Why This Problem Matters#

LeetCode 173 — Binary Search Tree Iterator — is a class-design favorite at Amazon, Google, Meta, and Apple. It tests three skills simultaneously: iterative inorder traversal with an explicit stack, on-demand work distribution (lazy evaluation), and amortized analysis.

The naive solution materializes the entire inorder sequence in memory, but the constraint O(h) memory rules that out. The interviewer is checking whether you can convert a recursive inorder DFS into a paused, resumable form using a stack — a skill that transfers to streaming JSON parsers, database B-tree cursors, and lazy iterators in many languages.

This is a classic onsite question for L4/L5 SDE positions because it benchmarks comfort with class invariants, stack mechanics, and amortized reasoning.

The Core Insight#

A standard recursive inorder traversal pushes the entire left spine, processes the node, then recurses right. To pause this work, store the left spine on an explicit stack at construction. Then next() pops the top, returns its value, and (if it has a right subtree) pushes the left spine of that right subtree.

Each node is pushed exactly once and popped exactly once across the whole iteration, giving amortized O(1) per next(). The stack never holds more than h nodes (one per level on the current "leftmost not-yet-visited" path), giving O(h) space.

Visual Dry Run#

BST: [7, 3, 15, null, null, 9, 20]. Initial left spine push: [7, 3].

hasNext() returns false when stack empties.

Solution (Optimal)#

from typing import Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self._push_left(root)
 
    def _push_left(self, node: Optional[TreeNode]) -> None:
        while node is not None:
            self.stack.append(node)
            node = node.left
 
    def next(self) -> int:
        node = self.stack.pop()
        if node.right is not None:
            self._push_left(node.right)
        return node.val
 
    def hasNext(self) -> bool:
        return len(self.stack) > 0

var BSTIterator = function(root) {
    this.stack = [];
    this._pushLeft = (node) => {
        while (node) {
            this.stack.push(node);
            node = node.left;
        }
    };
    this._pushLeft(root);
};
 
BSTIterator.prototype.next = function() {
    const node = this.stack.pop();
    if (node.right) this._pushLeft(node.right);
    return node.val;
};
 
BSTIterator.prototype.hasNext = function() {
    return this.stack.length > 0;
};

Time: Amortized O(1) per next() and hasNext() — each node enters and exits the stack exactly once. Space: O(h) — stack stores at most one node per tree level.

Common Mistakes#

• Materializing the entire inorder list in the constructor — violates the O(h) memory expectation.
• Pushing the right child unconditionally instead of only when popping — leads to incorrect ordering.
• Forgetting to push the left spine of node.right after popping; you'll skip values.
• Using recursion in next() to build the next value — the whole point is to avoid recursion.
• Reading hasNext as "any node remaining in tree" rather than "any node remaining in stack" — they're equivalent only because of the invariant.

Interview Tips#

• State the invariant clearly: "The stack always contains the path of unvisited ancestors of the next inorder node."
• Walk through one full sequence before coding.
• Mention that LC 510 Inorder Successor in BST II uses parent pointers for the same effect without a stack.
• Explain amortized O(1): n total pushes and pops over n calls.

Follow-up Questions#

• "Implement prev() for reverse traversal" — Mirror the structure: push right spine, pop, push right child's left spine.
• "Implement next(target) to skip ahead to first key >= target" — Use BST search to seed the stack.
• "Range iterator [lo, hi]" — Initialize stack with the path to lo, stop when popped value > hi.
• "Persistent BST iterator across mutations" — Use snapshot semantics or copy-on-write trees.
• "K-th smallest with this iterator" — Call next() k times.

Key Takeaways#

• LeetCode 173 BST Iterator implements iterative inorder with an explicit stack of left-spine ancestors.
• next() is amortized O(1) and hasNext() is O(1).
• Memory is O(h) — only the unvisited-ancestor path lives on the stack.
• The invariant: stack top is always the next inorder node.
• The same pattern powers database B-tree cursors and streaming serializer iterators.
• Asked at Amazon, Google, Meta, and Apple as a class-design tree question.
• LC 1586 BST Iterator II extends this with prev() and bidirectional navigation.