Binary Search Tree Iterator

medium bst stack iterator

Problem

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer.

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;
    }
};

Explanation

An in-order walk of a BST gives sorted values, but we want to produce them one at a time on demand, without traversing the whole tree up front. The answer is to simulate the recursion with an explicit stack.

The helper pushLeft(node) walks down the left edge, pushing every node it passes. After this, the top of the stack is always the smallest unseen value, because the leftmost node is the next one in sorted order.

In the constructor we run pushLeft(root) so the stack holds the left spine from the root down to the minimum.

Each next() pops the top node (that is the answer), then calls pushLeft on the popped node's right child. That brings the next batch of smaller-than-everything-remaining values onto the stack. hasNext() is just "is the stack non-empty?".

Example on [7,3,15,_,_,9,20]: the stack starts as [7,3]; popping gives 3, then 7 (and 7's right child 15 pushes 15,9), then 9, then 15, then 20 — sorted order.

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