Basic idea: use a stack to keep trace of the ancestors of current node.

The next smallest node could be found as the following rules:

`[0]`

start by keep go to left son from root:`root->left->...->left`

`[1]`

if the current node has a right son, go to`current->right->left->...->left`

`[2]`

else pop the stack until the father node has a bigger value (if cannot find such node, we've already finished)

For example, the tree `[5, 2, 6, 1, 4, null, null, null, null, 3]`

would be visited by applying rules like `[0]->[2]->[1]->[2]->[2]->[1]`

.

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