Code Implementation

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()
        val = node.val
        if node.right:
            self._push_left(node.right)
        return val

    def hasNext(self):
        return len(self.stack) > 0
      

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

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

var BSTIterator = function(root) {
    this.stack = [];
    this._pushLeft = function(node) {
        while (node) {
            this.stack.push(node);
            node = node.left;
        }
    };
    this._pushLeft(root);
};

BSTIterator.prototype.next = function() {
    let node = this.stack.pop();
    if (node.right) {
        this._pushLeft(node.right);
    }
    return node.val;
};

BSTIterator.prototype.hasNext = function() {
    return this.stack.length > 0;
};
      

Problem Description

You are given the root node of a binary search tree (BST) and asked to design an iterator over its elements. Your iterator should return the next smallest number in the BST each time you call next(), and indicate whether there is a next number with hasNext().

• Implement the BSTIterator class with the following methods:
• BSTIterator(TreeNode root): Initializes the iterator with the root node of the BST.
• int next(): Returns the next smallest number in the BST.
• boolean hasNext(): Returns true if there exists a next number; otherwise, false.
• Constraints:
• All calls to next() and hasNext() should run in average O(1) time.
• Extra memory usage must be O(h), where h is the height of the tree.
• You may assume that next() will always be called if hasNext() returns true.

Thought Process

To solve this problem, we need to simulate an in-order traversal of a BST, which naturally yields nodes in ascending order. A brute-force approach might be to traverse the entire tree at the start, store all values in a list, and then iterate through that list. While this would make next() and hasNext() trivial, it would use O(n) extra memory, which violates the O(h) space constraint.

Instead, we should only store enough information to know what the next smallest element is, without visiting the entire tree upfront. This leads us to use a stack to keep track of the path to the next node. Each time we need the next smallest element, we can pop from the stack, and if the popped node has a right child, we process its leftmost descendants. This way, we only use O(h) space and efficiently find the next element.

Solution Approach

The core idea is to simulate the in-order traversal iteratively using a stack:

1. Initialization: When the iterator is created, push all the left children of the root onto the stack. This ensures that the smallest element is on top.
2. next(): Pop the top node from the stack (the current smallest). If this node has a right child, push all its left descendants onto the stack. This updates the stack so that the next smallest node is always on top.
3. hasNext(): Simply check if the stack is non-empty.

Why a stack? The stack keeps track of the path from the root to the current node, allowing us to efficiently backtrack and find the next smallest element without traversing nodes multiple times.

• Each node is pushed and popped from the stack at most once.
• At any time, the stack contains at most h nodes, where h is the height of the BST.
• Both next() and hasNext() are O(1) on average.

Example Walkthrough

Consider the BST:

        7
       / \
      3   15
         /  \
        9    20
    

• Push 7 (root), then 3 (left child of 7) onto the stack.
• Stack: [7, 3] (top is 3)

• Pop 3 (no right child). Return 3.
• Stack: [7]

• Pop 7 (has right child 15). Push 15, then its left child 9.
• Stack: [15, 9]
• Return 7.

• Pop 9 (no right child). Return 9.
• Stack: [15]

• Pop 15 (has right child 20). Push 20.
• Stack: [20]
• Return 15.

• Pop 20 (no right child). Return 20.
• Stack: []

• Stack is empty. Return false.

Time and Space Complexity

Brute-force approach:

• Time: O(n) to traverse and store all nodes; O(1) per next() and hasNext().
• Space: O(n) for storing all node values.

• Time: O(1) on average per next() and hasNext(). Each node is pushed and popped once, so total O(n) over all operations.
• Space: O(h), where h is the height of the tree, since the stack only holds the path to the next node.

The use of a stack ensures we never exceed O(h) space, and the amortized cost per operation is constant.

Summary

The BST Iterator problem is elegantly solved by simulating in-order traversal with a stack, ensuring that each call to next() and hasNext() is efficient and uses minimal space. The key insight is to only maintain the path to the next smallest node, rather than all nodes, thus satisfying both the time and space constraints. This approach is both practical and widely applicable when you need to iterate through BSTs in sorted order.