Binary Search Tree Iterator

173.Binary Search Tree Iterator

Tree

Binary Search Tree

Stack

Design

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 an object containing the root of the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer. int next() Moves the pointer to the right, then returns the number at the pointer.

Example:

Input:

["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7,3,15,null,null,9,20]], [], [], [], [], [], [], []]

→

Output:

[null, 3, 7, true, 9, true, 15, true]

The iterator will return the elements in sorted order: [3,7,9,15,20]

Algorithm:

1. Use stack to maintain path to next smallest element
2. Initialize by pushing all left nodes from root
3. For next(), pop current node and process its right subtree
4. hasNext() checks if stack is non-empty

Complexity:

Time: O(1) average | Space: O(h) where h is height of tree

Java Solution:

class BSTIterator {
    Stack<TreeNode> s;

    public BSTIterator(TreeNode root) {
        s = new Stack<>();
        // Initialize stack with path to smallest element
        while (root != null) {
            s.push(root);
            root = root.left;
        }
    }

    public boolean hasNext() {
        // Next element exists if stack is not empty
        return (!s.isEmpty());
    }

    public int next() {
        // Get current smallest node
        TreeNode node = s.pop();
        
        // Push path to next smallest (left-most in right subtree)
        TreeNode next = node.right;
        while (next != null) {
            s.push(next);
            next = next.left;
        }
        
        return node.val;
    }
}

Python Solution:

class BSTIterator:
    def __init__(self, root: TreeNode):
        self.stack = []
        # Initialize stack with path to smallest element
        while root:
            self.stack.append(root)
            root = root.left
    
    def next(self) -> int:
        # Get current smallest node
        node = self.stack.pop()
        
        # Push path to next smallest (left-most in right subtree)
        curr = node.right
        while curr:
            self.stack.append(curr)
            curr = curr.left
            
        return node.val

    def hasNext(self) -> bool:
        # Next element exists if stack is not empty
        return len(self.stack) > 0

C++ Solution:

class BSTIterator {
private:
    stack<TreeNode*> s;
    
public:
    BSTIterator(TreeNode* root) {
        // Initialize stack with path to smallest element
        while (root) {
            s.push(root);
            root = root->left;
        }
    }
    
    int next() {
        // Get current smallest node
        TreeNode* node = s.top();
        s.pop();
        
        // Push path to next smallest (left-most in right subtree)
        TreeNode* curr = node->right;
        while (curr) {
            s.push(curr);
            curr = curr->left;
        }
        
        return node->val;
    }
    
    bool hasNext() {
        // Next element exists if stack is not empty
        return !s.empty();
    }
};