# C++ Non-recursive O(1) space, *NOT* Morris Traversal

• Well, I reckon I used kind of a hack, but it should work on almost all systems.
More importantly, this is non-recursive O(1) space but NOT Morris Traversal.
You can't find a similar one like this in any other post. This one is unique.
Other non-recursive O(1) space traversals in other posts are all based on Morris.

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
TreeNode *t, *p = root, *c = p ? p->left : NULL;
for (bool d = true, f = false; p; ) {
if (d && c) {
if (!c->left && !c->right) {
v.push_back(c->val);
d = false;
} else {
t = p;
p = c;
c = c->left;
p->left = (TreeNode*)~(uintptr_t)t;
f = false;
}
} else if (!f && ((d && !p->left) || (!d && p->left == c) || p->left > p->right)) {
v.push_back(p->val);
t = c;
c = p->right;
if (p->left != t) p->right = p->left;
p->left = t;
d = c ? true : false;
f = true;
} else {
if (p == root) break;
t = c;
c = p;
p = (TreeNode*)~(uintptr_t)p->right;
c->right = t;
d = false;
f = false;
}
}
return v;
}
};
``````

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