Flatten Binary Tree to Linked List

Problem

Flatten a binary tree to a linked list in-place. The list should use right pointers and be in pre-order order.

Key insight: For each node: save right child, make left child the right, append old right to end of new right chain. Set left = null.

Approach — Morris-like In-Place

Process node: find rightmost of left subtree, attach right child there, move left to right, null left.

Solutions

// C
void flatten(TreeNode* root) {
    while (root) {
        if (root->left) {
            TreeNode* tail = root->left;
            while (tail->right) tail = tail->right;
            tail->right = root->right;
            root->right = root->left;
            root->left = NULL;
        }
        root = root->right;
    }
}

// C++
void flatten(TreeNode* root) {
    while (root) {
        if (root->left) {
            auto tail = root->left;
            while (tail->right) tail = tail->right;
            tail->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }
        root = root->right;
    }
}

// Java
public void flatten(TreeNode root) {
    while (root != null) {
        if (root.left != null) {
            TreeNode tail = root.left;
            while (tail.right != null) tail = tail.right;
            tail.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        root = root.right;
    }
}

// JavaScript
function flatten(root) {
    while (root) {
        if (root.left) {
            let tail = root.left;
            while (tail.right) tail = tail.right;
            tail.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        root = root.right;
    }
}

# Python
def flatten(root):
    while root:
        if root.left:
            tail = root.left
            while tail.right:
                tail = tail.right
            tail.right = root.right
            root.right = root.left
            root.left = None
        root = root.right

Complexity

Time: O(n)
Space: O(1) — in-place, no recursion

Key Insight

Find the rightmost node of the left subtree — that's where the right subtree gets attached.