BST In-Order Iterator

medium bst stack iterator

Problem

Implement an iterator that returns BST values in sorted order via next() and hasNext(). Each call should be O(1) amortized; only O(h) memory may be used.

Maintain an explicit stack that always holds the in-order successors waiting to be visited — concretely, the left spine from the next un-visited node down to the smallest unseen value. next() pops the top, then walks the popped node's right child's left spine onto the stack.

Inputlevel-order: [7, 3, 15, _, _, 9, 20] · 5 calls to next()

Output3, 7, 9, 15, 20

level-order ('_' for null)

class BSTIterator:
    def __init__(self, root):
        self.stk = []
        self._push_left(root)
    def _push_left(self, node):
        while node:
            self.stk.append(node)
            node = node.left
    def has_next(self):
        return bool(self.stk)
    def next(self):
        node = self.stk.pop()
        self._push_left(node.right)
        return node.val

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

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

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

Time: O(1) amortized per call Space: O(h)