# Share my 20 line NON-recursive solution

• Using a stack to do pre-order traverse and build up the result while treversing:

``````void flatten(TreeNode *root) {
if(root == NULL)
return;
stack<TreeNode*> sk;
TreeNode* tail = NULL;
sk.push(root);

while(!sk.empty()){
TreeNode * cur = sk.top();
sk.pop();
if(cur->right != NULL)
sk.push(cur->right);
if(cur->left != NULL)
sk.push(cur->left);

if(tail != NULL){
tail->right = cur;
tail->left = NULL;
}
tail = cur;
}
return;
}``````

• Yep, the hint of this problem mentions that the node's right pointers points to the next node of a pre-order traversal.

• cool, and I think using a stack is essentially the same as using a recursive function, maybe faster?

• Simple code with a driver function

``````vector <TreeNode* > v;
void func(TreeNode *root)
{
if(root)
{
v.push_back(root);
func(root->left);
func(root->right);
}

}

void flatten(TreeNode *root) {
if(root==NULL)
return;

func(root);

for(int i=1 ; i<v.size() ; i++)
{
root->left=NULL;
root->right=v[i];
root=root->right;
}
}``````

• I think the problem want a IN PLACE solution

• You are right ! Here is IN PLACE solution: (which needs only O(1) space)

``````void flatten(TreeNode *root) {
if(!root)
return;
while(root){
if(root->left){
if(root->right){
TreeNode* rc = root->left;
while(rc->right){
rc = rc->right;
}
rc->right = root->right;
}
root->right = root->left;
root->left = NULL;
}
root = root->right;
}
}``````

• Yes the are essentially same but stack should be faster , since we avoid stuff like. function call stack pop , moving sp pointer ...

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