# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
self.nodes = []
while root:
self.nodes.append(root)
root = root.left
# @return a boolean, whether we have a next smallest number
def hasNext(self):
return len(self.nodes) > 0
# @return an integer, the next smallest number
def next(self):
ret = self.nodes.pop()
cur = ret.right
while cur:
self.nodes.append(cur)
cur = cur.left
return ret.val
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())
Simple Python solution


I think the time complexity of hasNext function is not O(1) in your case. I think we can add a counter to count the number of nodes in the self.nodes list, in this way the complexity of hasNext function can be reduced to O(1). Here is the code:
# @param root, a binary search tree's root node def __init__(self, root): self.nodes = [] self.count = 0 while root: self.nodes.append(root) self.count += 1 root = root.left # @return a boolean, whether we have a next smallest number def hasNext(self): return self.count > 0 # @return an integer, the next smallest number def next(self): ret = self.nodes.pop() self.count = 1 cur = ret.right while cur: self.nodes.append(cur) self.count += 1 cur = cur.left return ret.val

self.nodes is a list. Getting the length of a list takes O(1) time. List has an attribute recording its length. Please check here: https://wiki.python.org/moin/TimeComplexity