# Simple Morris traversal, C++ , average O(1) time and O(1) space .

• 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;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.