Flatten Binary Tree to Linked List

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.

Example 1:

Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [0] Output: [0]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Approach: Reverse Pre-order Traversal (In-Place)

Algorithm

1. Maintain a global prev pointer initialized to null
2. Traverse the tree in right -> left -> root order (reverse pre-order)
3. For each node, set its right to prev, its left to null, then advance prev to the current node
4. Processing right subtrees first ensures the linked list builds backward correctly

Time & Space Complexity

• Time Complexity: O(N) - every node is visited once
• Space Complexity: O(1) extra space besides the recursion stack (O(H))

Java Implementation

public class FlattenBinaryTreeToLinkedList {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    private TreeNode prev;

    /**
     * Flatten the binary tree into a linked list in pre-order (in-place).
     * @param root Root of the binary tree
     */
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        flatten(root.right);
        flatten(root.left);

        root.right = prev;
        root.left = null;
        prev = root;
    }

    // Test method
    public static void main(String[] args) {
        FlattenBinaryTreeToLinkedList f = new FlattenBinaryTreeToLinkedList();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);

        f.flatten(root);
        System.out.print("Output: [");
        for (TreeNode node = root; node != null; node = node.right) {
            System.out.print(node.val);
            if (node.right != null) {
                System.out.print(",null,");
            }
        }
        System.out.println("]");
        // Expected: [1,null,2,null,3,null,4,null,5,null,6]
    }
}

Alternative Approach: Iterative with Left-Subtree Splicing

public void flattenIterative(TreeNode root) {
    TreeNode current = root;
    while (current != null) {
        if (current.left != null) {
            TreeNode prev = current.left;
            while (prev.right != null) {
                prev = prev.right;
            }
            prev.right = current.right;
            current.right = current.left;
            current.left = null;
        }
        current = current.right;
    }
}

Example Walkthrough

For root = [1,2,5,3,4,null,6], reverse pre-order visits 6, 5, 4, 3, 2, 1:

1. Visit 6: prev=null -> right=null, prev=6
2. Visit 5: right=6, prev=5
3. Visit 4: right=5, prev=4
4. Visit 3: right=4, prev=3
5. Visit 2: right=3, prev=2
6. Visit 1: right=2, prev=1

Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6, matching pre-order.

Key Points

1. Reverse Pre-order: Processing right, left, then root lets each node point to the previously built head
2. Global Prev: Carries the already-flattened suffix across recursion
3. Left Cleared: Every node’s left pointer is set to null, satisfying the linked-list shape
4. O(1) Extra Space: The iterative splicing variant uses no extra space beyond pointers
5. Pre-order Order: The final chain matches pre-order traversal of the original tree