class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
self.root = root
self.path = []
next_node = self.root
while next_node:
self.path.append(next_node)
next_node = next_node.left
# @return a boolean, whether we have a next smallest number
def hasNext(self):
return len(self.path) != 0
# @return an integer, the next smallest number
def next(self):
res = self.path.pop()
if res.right:
succ = res.right
while succ:
self.path.append(succ)
succ = succ.left
return res.val
Concise python solution


I like this program. Better than what I wrote. But it is hard to think of this at the beginning. @youke, any experience of how you thought of this?