Use a stack to simulate inorder traversal on demand:
class BSTIterator:
def __init__(self, root):
self.stack = []
self._pushLeft(root)
def _pushLeft(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
self._pushLeft(node.right)
return node.val
def hasNext(self):
return len(self.stack) > 0
The stack holds the "path to current position." After returning a node, you push its right subtree's left spine.
Time: average for next() (each node pushed/popped exactly once across all calls). Space: for the stack.