The key to this problem is to store the values in a stack. In the constructor and next, we add all the next smallest nodes into the stack. The following code should be obvious after you run it on some examples.

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class BSTIterator {11 public:12     BSTIterator(TreeNode *root) {13         pushLeft(root);14     }15 16     /** @return whether we have a next smallest number */17     bool hasNext() {18         return !nodes.empty();19     }20 21     /** @return the next smallest number */22     int next() {23         TreeNode* node = nodes.top();24         nodes.pop();25         pushLeft(node -> right);26         return node -> val;27     }28 private:29     stack
     
       nodes;30     void pushLeft(TreeNode* node) {31         while (node) {32             nodes.push(node);33             node = node -> left;34         }35     }36 };37 38 /**39  * Your BSTIterator will be called like this:40  * BSTIterator i = BSTIterator(root);41  * while (i.hasNext()) cout << i.next();42  */