173. Binary Search Tree Iterator

Description

The BSTIterator class provides an iterator interface for a Binary Search Tree (BST). It allows iterating over the nodes of the BST in ascending order of their values.

Intuition

To efficiently iterate over the BST in ascending order without using extra space proportional to the size of the tree, an iterative approach utilizing a stack is employed.

Approach

1. Initialization (__init__()): - The constructor initializes a stack to store nodes during traversal. - It calls a helper method _leftmost_inorder() to push all left children of the root onto the stack, ensuring the smallest element is at the top.
2. Helper Method (_leftmost_inorder()): - This method pushes all left children of a given node onto the stack, effectively simulating the leftmost path of an inorder traversal.
3. Next Smallest Element (next()): - Pops the top element from the stack, which represents the next smallest element in the BST. - If the popped node has a right child, calls _leftmost_inorder() on the right child to push its left children onto the stack.
4. Has Next Element (hasNext()): - Checks if the stack is not empty, indicating there are more nodes to iterate over.

Complexity

Time Complexity:

• next() and hasNext() operate in amortized O(1) time since each node is pushed and popped exactly once from the stack.

Space Complexity:

• O(H), where H is the height of the BST. This is because the stack stores nodes up to the height of the tree during traversal.

This approach ensures efficient iteration over the BST while maintaining a space-efficient implementation.

Code

C++

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        inorderTraversal(root);
    }
    int next() {
        int val = nodes.front();
        nodes.pop_front();
        return val;
    }
    bool hasNext() {
        return !nodes.empty();
    }
private:
    std::deque nodes;
    
    void inorderTraversal(TreeNode* node) {
        if (!node) return;
        inorderTraversal(node->left);
        nodes.push_back(node->val);
        inorderTraversal(node->right);
    }
};

Python

class BSTIterator:
    
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self._leftmost_inorder(root)
        
    def _leftmost_inorder(self, node):
        while node:
            self.stack.append(node)
            node = node.left
    
    def next(self) -> int:
        topmost_node = self.stack.pop()
        if topmost_node.right:
            self._leftmost_inorder(topmost_node.right)
        return topmost_node.val
    
    def hasNext(self) -> bool:
        return len(self.stack) > 0

Java

class BSTIterator {
    private List nodes;
    private Iterator iterator;

    public BSTIterator(TreeNode root) {
        nodes = new ArrayList<>();
        inorderTraversal(root);
        iterator = nodes.iterator();
    }
    public int next() {
        return iterator.next();
    }
    public boolean hasNext() {
        return iterator.hasNext();
    }
    private void inorderTraversal(TreeNode node) {
        if (node == null) return;
        inorderTraversal(node.left);
        nodes.add(node.val);
        inorderTraversal(node.right);
    }
}

JavaScript

var BSTIterator = function(root) 
{
    this.arr = [];
    const go = (node) => {
        if (!node) return;
        go(node.left);
        this.arr.push(node.val);
        go(node.right);
    }
    go(root);
};
BSTIterator.prototype.next = function() 
{
    return this.arr.shift();
};
BSTIterator.prototype.hasNext = function() 
{
    return this.arr.length > 0;
};