Binary Search Tree Iterator

Problem

Implement BSTIterator that supports next() and hasNext(). next() returns the smallest in-order element.

Key insight: Use a stack. Initialize by pushing all left nodes. On next(), pop, then push all left of right child.

Solutions

// C++
class BSTIterator {
    stack<TreeNode*> st;
    void pushLeft(TreeNode* node) {
        while (node) { st.push(node); node = node->left; }
    }
public:
    BSTIterator(TreeNode* root) { pushLeft(root); }
    int next() {
        auto node = st.top(); st.pop();
        pushLeft(node->right);
        return node->val;
    }
    bool hasNext() { return !st.empty(); }
};

// Java
class BSTIterator {
    Deque<TreeNode> stack = new ArrayDeque<>();
    public BSTIterator(TreeNode root) { pushLeft(root); }
    void pushLeft(TreeNode node) {
        while (node != null) { stack.push(node); node = node.left; }
    }
    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }
    public boolean hasNext() { return !stack.isEmpty(); }
}

// JavaScript
class BSTIterator {
    constructor(root) {
        this.stack = [];
        this.pushLeft(root);
    }
    pushLeft(node) {
        while (node) { this.stack.push(node); node = node.left; }
    }
    next() {
        const node = this.stack.pop();
        this.pushLeft(node.right);
        return node.val;
    }
    hasNext() { return this.stack.length > 0; }
}

# Python
class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

    def hasNext(self):
        return bool(self.stack)

Complexity

next(): O(1) amortized
Space: O(h)

Key Insight

The stack always holds the "left spine" of the remaining right subtree. Each node is pushed and popped exactly once.