Total time complexity of traversing n nodes is O(3 * n), so average time complexity of each call is O(1). A pointer `TreeNode* nextp`

is used to indicate next smallest node. According to morris traversal algorithm if the right children of the predecessor of `nextp`

equal to `nextp`

, that means the left side of `nextp`

have been traversed, so `nextp`

should be itself. If the right children of the predecessor of `nextp`

equal to `NULL`

that means real next pointer should be the smallest of the left side of `nextp`

.

```
class BSTIterator {
private:
TreeNode* nextp;
public:
BSTIterator(TreeNode *root) {
nextp = root;
}
void MorrisTraversal(TreeNode* root)
{
if(root == NULL)
nextp = NULL;
else
{
TreeNode* cur = root;
while(cur->left != NULL)
{
//find the predecessor node of cur node
TreeNode* prenode = cur->left;
while(prenode->right != NULL && prenode->right != cur)
prenode = prenode->right;
//determine the next node
if(prenode->right == NULL)
{
prenode->right = cur;
cur = cur->left;
}
else
{
prenode->right = NULL;
nextp = root;
return;
}
}
nextp = cur;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
if(nextp == NULL)
return false;
else
return true;
}
/** @return the next smallest number */
int next() {
MorrisTraversal(nextp);
int tmp = nextp->val;
nextp = nextp->right;
return tmp;
}
};
```