Just apply iterative inorder traversal (Leetcode 94), in a oop design.
class BSTIterator:
def __init__(self, root: TreeNode):
self.stack = []
self.root = root
def next(self) -> int:
"""
@return the next smallest number
"""
while(self.stack or self.root):
if self.root:
self.stack.append(self.root)
self.root = self.root.left
else:
node = self.stack[-1]
self.stack.pop()
self.root = node.right
return node.val
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return self.stack or self.root