Flatten Binary Tree to Linked List

Problem

You are given the root of a binary tree. Flatten it in place into a “linked list”:

• Reuse the existing TreeNode objects. For every node, set its left child to None and its right child to the next node in the flattened order.
• The order must match a pre-order traversal of the original tree (visit the node, then its left subtree, then its right subtree).

After flattening, the whole tree is a right-leaning chain: following right pointers from the root visits every node exactly once in pre-order, and every left pointer is None.

Examples

Example 1

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

Pre-order is 1,2,3,4,5,6. The result is that sequence linked entirely through right pointers.

Example 2

Input: root = []
Output: []

An empty tree stays empty.

Example 3

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

A single node is already a valid flattened list.

Constraints

• The number of nodes is in the range [0, 2000].
• -100 <= Node.val <= 100
• Aim to do it in place; a follow-up asks for O(1) extra space (beyond the recursion/traversal, ideally constant auxiliary memory).

Think about it first

TL;DR

Morris-style pointer rewiring flattens in pre-order with O(1) extra space; O(n) time. (Recursive variants use O(h) stack.)

Approach 1 — Brute force: collect pre-order, then relink

The naive idea separates the two concerns: first record every node in pre-order into a list, then walk the list and rewire left = None, right = next node.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        nodes: List[TreeNode] = []

        def preorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            nodes.append(node)
            preorder(node.left)
            preorder(node.right)

        preorder(root)
        for i in range(len(nodes) - 1):
            nodes[i].left = None
            nodes[i].right = nodes[i + 1]
        if nodes:
            nodes[-1].left = None
            nodes[-1].right = None

Complexity: O(n) time, O(n) space for the node list plus O(h) recursion. Correct and simple, but it uses linear auxiliary memory — the follow-up wants O(1).

Approach 2 — Recursive flatten returning the tail

The insight: to flatten a node, flatten its left and right subtrees first, then splice: the node’s right becomes the flattened left chain, and the tail of that left chain connects to the flattened right chain. If each recursive call returns the last node of the chain it produced, the parent can stitch in O(1) without re-walking.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        def flatten_return_tail(node: Optional[TreeNode]) -> Optional[TreeNode]:
            if not node:
                return None
            left_tail = flatten_return_tail(node.left)
            right_tail = flatten_return_tail(node.right)

            if left_tail:  # splice the left chain between node and its right
                left_tail.right = node.right
                node.right = node.left
                node.left = None

            # New tail: rightmost of (right_tail, left_tail, node), in that order.
            return right_tail or left_tail or node

        flatten_return_tail(root)

Walkthrough on Example 1 (root = [1,2,5,3,4,null,6], i.e. 1 has left 2(children 3,4) and right 5(right child 6)):

1. Flatten node 3: leaf → tail 3. Node 4: leaf → tail 4.
2. Flatten node 2: left_tail = 3, right_tail = 4. Splice: 3.right = 4 (node 2’s old right), 2.right = 2.left (node 3), 2.left = None. Chain 2 → 3 → 4, returns tail 4.
3. Flatten node 6: leaf → tail 6. Node 5: left_tail = None, right_tail = 6; no left splice; returns 6.
4. Flatten root 1: left_tail = 4, right_tail = 6. Splice: 4.right = 1.right (node 5), 1.right = 1.left (node 2), 1.left = None. Chain: 1 → 2 → 3 → 4 → 5 → 6. ✓

Complexity: O(n) time, O(h) space for the recursion stack — no auxiliary list, but the stack is not strictly O(1).

Approach 3 — Morris-style in-place, O(1) space

The insight: you can flatten with a single moving pointer and no recursion. At each node with a left child, find the rightmost node of the left subtree (that subtree’s pre-order last node); attach the current node’s right subtree there, move the entire left subtree to the right, and null the left. Then advance right. This is the same rewiring trick used in Morris traversal (threading a subtree’s tail to the successor).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        curr = root
        while curr:
            if curr.left:
                # Rightmost node of the left subtree = its pre-order tail.
                rightmost = curr.left
                while rightmost.right:
                    rightmost = rightmost.right
                # Splice current right subtree after that tail.
                rightmost.right = curr.right
                curr.right = curr.left
                curr.left = None
            curr = curr.right

Walkthrough on Example 1 again, starting at 1:

1. curr = 1, has left 2. Rightmost of left subtree (2 → ... → 4 after 2’s own subtree, but at this moment 2’s subtree is 2 with children 3,4; its rightmost is 4). Set 4.right = 5 (old right), 1.right = 2, 1.left = None. Advance curr = 2.
2. curr = 2, has left 3. Rightmost of 3 is 3. 3.right = 4 (2’s current right), 2.right = 3, 2.left = None. Advance curr = 3.
3. curr = 3, no left → advance to 4. 4 no left → advance to 5. 5 no left → advance to 6. 6 no left → advance to None. Done.
4. Chain 1 → 2 → 3 → 4 → 5 → 6, all left = None. ✓

Complexity: O(n) time — each edge is traversed a constant number of times (the inner “find rightmost” walks each right-spine edge at most twice overall). O(1) extra space. This is the answer to the follow-up.

Common pitfalls

• Wrong order of the splice: you must save curr.right before overwriting it with curr.left. Attach the old right subtree to the left subtree’s tail first, then move the left subtree over.
• Forgetting left = None: the result must have every left pointer null; leaving stale left pointers produces an invalid flattened list.
• Finding the wrong tail: the attach point is the rightmost node of the left subtree (its pre-order last), not the left child itself — otherwise you overwrite a real subtree.
• Recursive order: flatten the left and right subtrees before rewiring the current node; rewiring first corrupts the pointers you still need to recurse into.
• Empty tree: guard None — Approach 3’s while curr and the recursive base cases both handle it, returning nothing.

Pattern takeaway

“Restructure a tree in place into a specific traversal order” is solved by identifying, for each node, the tail of the sub-chain that must precede its remaining subtree, and threading that tail to the successor. Returning the tail from recursion (Approach 2) or finding it with a rightmost-walk (Approach 3, Morris) avoids repeated scanning and, in the Morris case, achieves O(1) space.