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
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?