Flatten Binary Tree to Linked List — Morris-Style In-Place Explained

Problem Statement

LeetCode 114 — Flatten Binary Tree to Linked List Difficulty: Medium | Pattern: Morris-Style In-Place Tree Manipulation

Given the root of a binary tree, flatten the tree into a linked list in-place. The linked list should use the same TreeNode class where the right child pointer points to the next node 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.

Constraints:

Number of nodes: 0 <= n <= 2000
-100 <= Node.val <= 100

Example:

Input:
        1
       / \
      2   5
     / \   \
    3   4   6
 
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
(as right pointers; all left pointers are null)
 
Pre-order: 1, 2, 3, 4, 5, 6

Why This Problem Matters

This problem is asked at Microsoft, Amazon, and Google specifically because it requires knowledge of binary tree pre-order traversal combined with in-place pointer manipulation — two distinct skills that must work together. It also has three distinct solution approaches with different time-space tradeoffs, making it rich for discussion.

In practice, flattening a tree to a linked list appears in serialization algorithms, where tree structures must be written to a linear medium (files, streams). Pre-order flattening is the natural approach because the root always comes first, followed by the left subtree and then the right subtree.

The most impressive solution — the Morris-style iterative approach — runs in O(n) time and O(1) space, achieving constant extra space by cleverly reusing left-subtree pointers rather than using a stack. This approach shows deep familiarity with tree structure and is the answer that distinguishes candidates from each other at senior-level interviews.

Understanding this problem also directly prepares you for "Binary Tree Right Side View," "Binary Tree Zigzag Order Traversal," and any problem that requires restructuring a tree in-place.

The Core Insight

The Morris-style approach works by repeatedly performing the following operation until the tree is a right-only chain:

For each node curr that has a left child:

Find the rightmost node of the left subtree (call it pre). This is the node that should come just before curr.right in pre-order.
Connect pre.right = curr.right — attach the right subtree of curr to the end of the left subtree.
Move curr.left to curr.right — the left subtree becomes the right child.
Set curr.left = null — clear the left pointer.
Advance curr = curr.right and repeat.

This mimics what you would do if you were inserting the left subtree into the chain at the correct pre-order position.

Visual Dry Run

Input tree:

Step 1: curr = node(1), has left child

Left subtree: 2 -> 3, 2 -> 4
Rightmost of left subtree: node(4)
Connect node(4).right = node(5)
Move node(2) to right: node(1).right = node(2)
Set node(1).left = null

Step 2: curr = node(2), has left child

Left subtree: 3
Rightmost of left subtree: node(3)
Connect node(3).right = node(4)
Move node(3) to right: node(2).right = node(3)
Set node(2).left = null

1 -> 2 -> 3 -> 4 -> 5 -> 6  (all via right pointers)

Solution (Optimal — Morris Style)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def flatten(root: 'TreeNode') -> None:
    """Modifies the tree in-place. Returns None."""
    curr = root
    while curr:
        if curr.left:
            # Find the rightmost node of the left subtree
            pre = curr.left
            while pre.right:
                pre = pre.right
 
            # Attach right subtree to end of left subtree
            pre.right = curr.right
 
            # Move left subtree to right
            curr.right = curr.left
            curr.left = None
 
        # Advance to next node (now curr.right)
        curr = curr.right

function flatten(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            // Find rightmost node of left subtree
            let pre = curr.left;
            while (pre.right) {
                pre = pre.right;
            }
 
            // Attach right subtree after left subtree
            pre.right = curr.right;
 
            // Move left subtree to right position
            curr.right = curr.left;
            curr.left = null;
        }
 
        curr = curr.right;
    }
}

Complexity:

Metric	Value
Time	O(n) — each node is visited at most twice (once as curr, once as pre)
Space	O(1) — in-place, no stack or recursion

Simpler recursive approach (O(h) space):

def flatten(root):
    def dfs(node):
        if not node:
            return None
        if not node.left and not node.right:
            return node  # leaf: return itself as the tail
 
        left_tail = dfs(node.left)
        right_tail = dfs(node.right)
 
        if left_tail:
            left_tail.right = node.right
            node.right = node.left
            node.left = None
 
        return right_tail if right_tail else left_tail
 
    dfs(root)

Common Mistakes

Losing the right subtree before attaching it: In the Morris approach, you must connect pre.right = curr.right BEFORE setting curr.right = curr.left. Reversing these two assignments loses the right subtree.
Forgetting to null the left pointer: After moving left to right, always set curr.left = null. Leaving it populated corrupts the "linked list" format.
Confusing in-order with pre-order: The problem requires pre-order (root, left, right). The Morris approach naturally produces pre-order because you process the left subtree before the right.
Not advancing curr correctly: After the transformation, advance with curr = curr.right (not curr = curr.left which is now null).
Using a stack and not noting the space cost: The stack-based iterative approach is O(h) space. If the interviewer asks for O(1) space, you must use the Morris-style approach.

Interview Tips

Offer three approaches: Stack-based iterative (O(n) space), recursive post-order (O(h) space), and Morris-style in-place (O(1) space). Interviewers appreciate seeing the progression.
Explain the Morris invariant: "For each node with a left child, I find the rightmost node of the left subtree — the node that should immediately precede the right subtree in pre-order — and stitch them together."
Draw the tree transformation: Show the tree before and after step 1, step 2, etc. This makes the algorithm's correctness obvious.
Clarify in-place: "The problem says in-place and the function signature returns void — so I modify the tree directly without allocating new nodes."
Mention practical application: "This is essentially the step you would do to serialize a binary tree to a pre-order string, reusing the existing node structure."

Follow-up Questions

Flatten to in-order linked list: The Morris approach needs to be modified — the in-order sequence differs from pre-order.
Can you reconstruct the tree from the flattened list? Yes, if you know the structure. Discuss how to do it.
LeetCode 427 — Construct Quad Tree: Another in-place tree structure manipulation problem.
What if the tree is very deep (n = 2000)? The recursive approach risks stack overflow. Prefer the Morris iterative approach for large inputs.
How does this relate to the rope data structure? Ropes flatten binary tree-like structures to represent strings — the underlying operation is similar.
LeetCode 116 — Populating Next Right Pointers: A related problem where you add horizontal pointers between nodes at the same level, also amenable to O(1) space approaches.

Key Takeaways

The Morris-style approach flattens the tree in O(n) time and O(1) space by reusing the right-child pointer to stitch left subtrees into a right-only chain.
For each node with a left child: find the rightmost node of the left subtree, attach the right subtree there, move the left subtree to the right, and null the left pointer.
Pointer assignment order matters: attach pre.right = curr.right before reassigning curr.right = curr.left.
The flattened list follows pre-order traversal — root, then left subtree, then right subtree.
Three approaches exist with different space costs: iterative with stack (O(n)), recursive (O(h)), and Morris-style (O(1)). Know all three.
This problem bridges tree and linked list knowledge — a common interview theme that tests breadth of data structure understanding.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal — Morris Style)#

Common Mistakes#

Interview Tips#

Follow-up Questions#

Key Takeaways#

Related reading