Problem - BST Iterator

Implement an iterator over a BST with:

• BSTIterator(root): Initialize with BST root
• next(): Return the next smallest element
• hasNext(): Return whether next element exists

Both operations should run in average $O(1)$ time and use $O(h)$ memory.

Example: For BST $[7,3,15,null,null,9,20]$, calling next() repeatedly should return $3, 7, 9, 15, 20$.

This tests your understanding of controlled iteration versus full traversal. Constraints: up to $10^5$ nodes, at most $10^5$ calls total.