Flatten Binary Tree to Linked List

Practice Link

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The "linked list" should be in the same order as a pre-order traversal of the binary tree.

RECURSION#

Process the tree in reverse pre-order (right subtree → left subtree → root). Maintain a prev pointer tracking the last node processed. After recursing into both subtrees, set root->right = prev and root->left = NULL, then update prev = root. Because we process right before left before root, the chain builds in the correct pre-order direction from tail to head. Uses O(h) stack space for the recursion depth.

class Solution {
public:
    TreeNode* prev=NULL;

    void flatten(TreeNode* root) {
        if(!root)
            return;
        flatten(root->right);
        flatten(root->left);

        root->right = prev;
        prev= root;
        root->left = NULL;
    }
};

USING STACK#

Simulate a pre-order traversal iteratively with an explicit stack. Pop the current node, push its right child then left child (so left is processed first). Set the current node's right to the stack's new top (the next node in pre-order) and left to null. This rewires the tree in-place as we traverse. Uses O(h) stack space like the recursive approach but avoids system call-stack overhead.

class Solution {
public:
    void flatten(TreeNode* root) {

        if(!root)
            return;
        stack<TreeNode*> stk;
        stk.push(root);

        while(!stk.empty())
        {
            TreeNode* curr = stk.top();
            stk.pop();

            if(curr->right)
                stk.push(curr->right);
            if(curr->left)
                stk.push(curr->left);
            if(!stk.empty())
                curr->right = stk.top();
            curr->left = NULL;

        }
    }
};

MORRIS MODIFIED#

Achieve O(1) space by threading the tree. For each node with a left subtree, find the rightmost node in the left subtree (findPredicate). Connect that node's right to the current node's original right child. Then make the left subtree the new right child and clear the left pointer. Advance curr to the right. This effectively inserts the left subtree between the current node and its original right subtree, building the pre-order list in-place without any auxiliary stack.

class Solution {
public:

    TreeNode* findPredicate(TreeNode* root)
    {
        while(root->right)
        {
            root=root->right;
        }
        return root;
    }

    void flatten(TreeNode* root) {
        TreeNode* curr = root;

        while(curr)
        {
            if(curr->left)
            {
                TreeNode* prev = findPredicate(curr->left);

                prev->right = curr->right;
                curr->right = curr->left;
                
                curr->left = NULL;
            }
            curr=curr->right;
        }
    }
};