Binary Search Tree Iterator

Problem

Implement an iterator that walks a binary search tree in ascending order of value.

• BSTIterator(root) is constructed from the root of a BST.
• next() returns the smallest value that has not yet been returned. It is only called when a value remains.
• hasNext() returns True if any value remains to be returned.

next() and hasNext() should run in O(1) amortised time, and the iterator should use O(h) memory, where h is the height of the tree, rather than O(n).

• The tree has at least one node, and up to about 200,000 nodes total.
• Node values are non-negative integers and fit comfortably in a signed 32-bit int.
• The combined number of next and hasNext calls stays within a similar order of magnitude, so per-call cost matters more than a constant-factor overhead.

Examples

• root = [5, 2, 11, None, None, 8, 17]: next() → 2, next() → 5, hasNext() → True, next() → 8, next() → 11, next() → 17, hasNext() → False.
• root = [9]: hasNext() → True, next() → 9, hasNext() → False.
• root = [4, 3, None, 2] (a left-leaning chain): the calls return 2, 3, 4 in that order.

Hints

1. Which traversal of a BST yields ascending order, and what does the iterative version of it keep on its stack?
2. After returning a node, what is the smallest value larger than it, and where in the tree does it live relative to that node's right child?
3. Keep a stack of the current left spine; next() pops the top and then pushes the left spine of the popped node's right child.