Binary Search Tree Iterator

TreeNode(val, left=None, right=None) is in the starter. Keep it.

In a binary search tree, every value in a node's left subtree is smaller than the node's value and every value in its right subtree is larger, so an in-order walk (left subtree, node, right subtree) meets the values in increasing order. Build a class BSTIterator that hands them out one at a time:

• BSTIterator(root) sets up the iterator. root may be None (an empty tree).
• next() returns the smallest value not handed out yet. It is only called when such a value exists.
• has_next() returns True if there are values left and False otherwise. It doesn't use one up.

#        7
#       / \
#      3   12
#     / \    \
#    1   5    15
it = BSTIterator(root)
it.next()       # 1
it.next()       # 3
it.has_next()   # True
it.next()       # 5
it.next()       # 7
it.next()       # 12
it.has_next()   # True
it.next()       # 15
it.has_next()   # False

• Up to 131,071 nodes with distinct values. Trees can be up to 2,000 levels deep: if you recurse, raise the limit first (sys.setrecursionlimit(10_000)).
• Flattening the whole tree into a sorted list in the constructor passes. For a better answer, use O(h) memory, where h is the tree's height, with next() and has_next() taking O(1) time on average.

⭐ Bonus: a speed test that walks a 131,071-node tree earns a star when each call takes O(1) time on average. Redoing an in-order walk on every call is too slow.