In order to solve the problem we need to have a in-order traversal on the tree so that we can return the smallest val and then the second smallest, the third smallest...

We can implement in-order traversal in a recursive way, but using stack we can write a better one. First of all, push the root, root->left, root->left->left, .... into the stack. For each time we pop a node, just check its right child, if it has a right child, push the right-child, right-child->left, right-child->left->left, .... Similar idea to

ChuntaoLu, pavel-shlyk and scott's.

```
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
sta = stack<TreeNode*>();
for(TreeNode *cur=root; cur; cur=cur->left) {
sta.push(cur);
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !sta.empty();
}
/** @return the next smallest number */
int next() {
TreeNode *cur = sta.top();
sta.pop();
for(TreeNode *i=cur->right; i; i=i->left) {
sta.push(i);
}
return cur->val;
}
private:
stack<TreeNode*> sta;
};
```