# 8ms, Non-recursive, No stack, C++ solution

• ``````void flatten(TreeNode *root) {
while (root) {
if (root->left && root->right) {
TreeNode* t = root->left;
while (t->right)
t = t->right;
t->right = root->right;
}

if(root->left)
root->right = root->left;
root->left = NULL;
root = root->right;
}
}``````

• A bit different though but my code ended up almost the same as yours :)

``````var flatten = function(root) {
while (root) {
if (root.left) {
var t = root.left;
while (t.right) {
t = t.right;
}
t.right = root.right;
root.right = root.left;
root.left = null;
}
root = root.right;
}
};
``````

And later I found out your solutions is better, and tweak it a bit as the following. There's no need to set left to null if it's already null. But anyway, this wont improve too much :)

``````var flatten = function(root) {
while (root) {
if (root.left && root.right) {
var t = root.left;
while (t.right) {
t = t.right;
}
t.right = root.right;
}

if (root.left) {
root.right = root.left;
root.left = null;
}
root = root.right;
}
};
``````

• Excuse me, but what is the time complexity of this algorithm? Thanks.

• The time complexity is O(n). We visit every single node only one time.

• When flattening every TreeNode, it will go down to find the last element of left subtree. So I think it is O(nlogn).

• @xiesheng I think each node will be visited at most two times, so the run time should be O(n)

• @for_the_glory As @xiesheng said, every step, you need to find left subtree's deepest right element. Many nodes will be visited much more than 2 times.

• Awesome and beautiful!

• 3ms

``````class Solution {
private:
TreeNode* flattenAux(TreeNode* root) {
if(!root) return NULL;
TreeNode *l = root->left, *r = root->right, *tmp = root;
root->left = NULL;
if(l) {
tmp = flattenAux(l);
root->right = l;
root = tmp;
}
if(r) {
tmp = flattenAux(r);
root->right = r;
}
return tmp;
}
public:
void flatten(TreeNode* root) {
flattenAux(root);
}
};
``````

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