Binary Search Tree Iterator
Implement an iterator over a binary search tree that returns the next smallest number.
Examples
Input: [["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"],[[[7,3,15,null,null,9,20]],[],[],[],[],[],[],[],[],[]]]
Output: [null,3,7,true,9,true,15,true,20,false]
Input: [["BSTIterator","hasNext","next","hasNext","next","hasNext"],[[[2,1,3]],[],[],[],[],[]]]
Output: [null,true,1,true,2,true]
Hints
Utilize recursion to perform an inorder traversal and store the sorted elements in a list, then iterate through the list for `next()` and `hasNext()` operations.
Implement an iterative inorder traversal using a stack to simulate the recursion, pushing left children onto the stack until reaching the leftmost node, then popping and processing nodes as you traverse right.
Optimize space by storing only the path to the current node in the stack (parent pointers), and implement `hasNext()` by checking if the stack is non-empty, while `next()` involves popping the top node and pushing its right subtree's leftmost path.
Related Problems
Binary Search Tree Iterator
Implement an iterator over a binary search tree that returns the next smallest number.