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