# C++ Non-recursive O(1) space solution, based on Morris Traversal

• Yes, Morris again. Praise Morris.
Traverse the tree only once with constant space.
No nasty global variables, and not really using the previous-first-second method.

``````class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *s[3][2], *p, *h = root;
int v, n = 0;
bool f = false;
while (h) {
if (p = h->left) {
while (p->right && p->right != h) p = p->right;
if (p->right) {
s[n][1] = h;
if (h->val < v) n++;
s[n][0] = h;
v = h->val;
h = h->right;
p->right = NULL;
} else {
p->right = h;
h = h->left;
}
} else {
s[n][1] = h;
if (f && h->val < v) n++;
s[n][0] = h;
v = h->val;
h = h->right;
f = true;
}
}
if (n==2) swap(s[0][0]->val, s[1][1]->val);
else swap(s[0][0]->val, s[0][1]->val);
}
};
``````

• Your's are really really O(1) space, some others said there recursive are O(1), but I think it is O(depth of tree), function calling stack should also be called SPACE.

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