```
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
TreeNode *current = NULL;
stack<TreeNode*> s;
public:
BSTIterator(TreeNode *root) {
// initialize the current pointer
current = root;
}
/** @return whether we have a next smallest number */
bool hasNext() {
while(current){
s.push(current);
current = current->left;
}
if(s.empty()){
return false;
}
return true;
}
/** @return the next smallest number */
int next() {
TreeNode* node = s.top();
s.pop();
current = node->right;
return node->val;
}
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
```

The basic idea behind this solution is that we have to implement inorder iteratively but it will gets split into two functions i.e. hasNext and next.

hasNext() will push all the left elements and check and return accordingly if elements are in the stack.

next() will just pop() the top element from the stack and update the current pointer to right .

For this we are taking a stack and a current pointer.

But maybe I may be wrong in hasNext as the requirement of question is O(1) for hasNext() as well.

Open for comments.