LeetCode 173: Binary Search Tree Iterator

Explanation

To implement the BSTIterator class, we can leverage the fact that an inorder traversal of a binary search tree gives the elements in sorted order. We can simulate the inorder traversal using a stack to keep track of the nodes as we traverse the tree. The constructor initializes the stack with all left children of the root. The next() function returns the next smallest element in the BST by popping from the stack and pushing the right children of the popped node. The hasNext() function returns true if the stack is not empty.

Time Complexity

• Constructor: O(h) average case
• hasNext(): O(1)
• next(): Amortized O(1)

Space Complexity

O(h) where h is the height of the tree.

class BSTIterator {
    Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushLeftChildren(root);
    }

    public int next() {
        TreeNode node = stack.pop();
        pushLeftChildren(node.right);
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    private void pushLeftChildren(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}