DSA problem
Binary Search Tree Iterator
Implement the BSTIterator class that represents an iterator over the inorder traversal of a Binary Search Tree (BST):
BSTIterator(TreeNode root) initializes the iterator. The pointer should be initialized to a non-existent number smaller than any element in the BST. next() moves the pointer to the right (next smallest) number and returns that number. hasNext() returns true if there exists a number on the right side of the pointer, otherwise false.
The naive implementation is to perform a full inorder traversal in the constructor, store every value in a list, and serve next() by index. That is correct but uses O(n) memory upfront, regardless of how many calls the consumer will make. The interview goal is to achieve O(1) memory beyond the input — measured in non-recursive auxiliary storage — and to have next() return in O(1) amortized time.
The optimal approach is a controlled iterative inorder traversal. In the constructor, push the chain of leftmost ancestors of the root onto a stack — this is exactly the prefix that a normal inorder traversal would push before producing its first value. Each call to next() pops the top of the stack to return its value, then pushes the leftmost chain of that node's right child to set up the following call.
Pushing the leftmost chain takes O(h) work in the worst case, but each node is pushed and popped at most once over the lifetime of the iterator, so across n calls to next() the total work is O(n) — that is amortized O(1) per call. The stack never holds more than h nodes at a time, giving O(h) auxiliary space rather than O(n).
Examples
["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"]
[[[7,3,15,null,null,9,20]],[],[],[],[],[],[],[],[],[]][null,3,7,true,9,true,15,true,20,false]Constructor on [2,1,3]; then next(), next(), next(), hasNext()1,2,3,falseConstructor on [1]; then hasNext(), next(), hasNext()true,1,falseConstraints
- The number of nodes in the tree is in the range [1, 10^5].
- 0 <= Node.val <= 10^6
- At most 10^5 calls will be made to hasNext and next.
- next() and hasNext() should run in average O(1) time and use O(h) memory.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.