# Simple Python solution

• # 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())

• 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

• Not needed. Getting the length of a list takes O(1) time

• I think you use len() function takes O(1) time, while you call len() it needs scan the list, so time is O(n).

• 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

• Nice, thanks~

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.