*Solution(1):*

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

*Solution(2):*

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