# C++ worst case O(1) time O(1) space solution, inspired by Morris Traversal

• Even in worst case, the time complexity of `hasNext()` and `next()` are both O(1). Not just average O(1), but constant O(1).
The time complexity of constructor `BSTIterator()` is O(n). (Be aware: The problem doesn't have time complexity requirement on constructor.) Proper destructor is also provided.
The space complexity is also O(1). No stack, no vector, no list, no queue, nothing.

61 / 61 test cases passed
Status: Accepted
Runtime: 19 ms

``````class BSTIterator {
private:
TreeNode *r, *h = NULL, *t = NULL;
public:
BSTIterator(TreeNode *root) {
r = root;
while (root) {
if (TreeNode *p = root->left) {
while (p->right && p->right != root) p = p->right;
if (p->right) {
if (root->right && root->right->left) t = root;
else t = NULL;
root = root->right;
} else {
p->right = root;
root = root->left;
}
} else {
if (!h) h = root;
if (t) t->right = root;
t = root;
root = root->right;
}
}
t = h;
}

~BSTIterator() {
for( ; h; h = t) {
t = h->right;
if (h != r) h->left = NULL;
if (t == r) h->right = NULL;
}
}

bool hasNext() {
return t;
}

int next() {
int v = t->val;
t = t->right;
return v;
}
};
``````

• but it actually change an BST into a "list", an Iterator should not change the original data structure. right?

• @xuyeiie Yes, but the problem doesn't say you can't touch the tree itself.
Besides, all other iteration method doesn't support add node or delete node either, so the tree is static.

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