Notice that next() is required to have O(1), so the processing of finding is in hasNext()

```
class BSTIterator(object):
def __init__(self, root):
self.root = root
self.stack = []
self.nxt = None
def hasNext(self):
while self.root:
self.stack.append(self.root)
self.root = self.root.left
else:
if not self.stack:
return False
tmp = self.stack.pop()
self.nxt = tmp.val
self.root = tmp.right
return True
def next(self):
return self.nxt
```