Binary Search Tree Iterator

Binary Search Tree Iterator

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• BSTIterator(root): Initializes the iterator with the root of the BST.
• next(): Returns the next smallest number in the BST.
• hasNext(): Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.

Examples

Example 1:

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]

      7
     / \
    3  15
       / \
      9  20

Constraints

• 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.

Expected Complexity

• next() and hasNext() should run in average O(1) time.
• Uses O(h) memory where h is the height of the tree.