My thought was very straight-forward by doing all the heavy work in the constructor in which traverse the tree and save all node in in-order sequence. Thus all remaining task for hasNext() and next() is quite simple...

But I doubt that this solution will persuade my interviewer! Ohhhhh!

**Any hints for a satisfactory solution?**

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