Binary Search Tree In-Order Iterator

Create a BSTIterator class that walks through the values of a binary search tree (BST) in in-order sequence:

BSTIterator(TreeNode root)
boolean hasNext()
int next()

• BSTIterator(TreeNode root) constructs the iterator using root as the tree's root. Before iteration begins, its pointer is positioned conceptually at a value that does not exist and is less than every value in the tree.
• boolean hasNext() reports whether another value appears after the current pointer position. Return true when one exists and false otherwise.
• int next() advances the pointer by one position in the traversal and returns the value reached.

Because iteration starts below every tree value, the first call to next() produces the smallest value in the BST.

You may rely on every call to next() being valid: whenever it is invoked, another value remains in the in-order traversal.

Aim for an implementation that requires O(h) additional memory, where h denotes the height of the tree.

Examples

Example 1:

Input:
["BSTIterator", "next", "hasNext", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[10, 4, 18, null, null, 13, 21]], [], [], [], [], [], [], [], [], []]

Output: [null, 4, true, 10, 13, true, 18, true, 21, false]

Explanation: The tree's in-order sequence is 4, 10, 13, 18, 21, so each next() returns the next value in that order and hasNext() becomes false only after the final value.

Constraints

• The tree contains between 1 and 10^5 nodes, inclusive.
• 0 <= Node.val <= 10^6
• Across the entire usage of the iterator, there are no more than 10^5 calls to hasNext and next combined.