Flatten Binary Tree to Linked List

Difficulty: Medium
Topics: Linked List, Stack, Tree, Depth-First Search, Binary Tree
Link: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Problem Description

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)?

Solution

1. Problem Deconstruction

Technical Reformulation: Given a binary tree’s root node, restructure the tree in-place such that:

Every node’s right child becomes the next node in a pre-order traversal sequence
Every node’s left child becomes null
The final structure should be a right-skewed linked list maintaining pre-order ordering
Time complexity should be optimized given N ∈ [0,2000] nodes
Space complexity should ideally be O(1) excluding recursion stack

Beginner-Friendly Version: Imagine you have a family tree diagram. We want to rearrange it into a straight line where:

Each person points only to the next person in a specific order
The order is: current person → all left-side descendants → all right-side descendants
We must rearrange the connections without creating new people, just rewiring pointers
The final structure should look like a chain going only downward

Mathematical Formulation: Let T be a binary tree with nodes V = {v₁, v₂, …, vₙ} Define pre-order traversal sequence P = (p₁, p₂, …, pₙ) where:

p₁ = root
∀i ∈ [1,n-1]: pᵢ₊₁ is the next node in pre-order traversal

Transform T such that:

left(pᵢ) = NULL ∀i ∈ [1,n]
right(pᵢ) = pᵢ₊₁ ∀i ∈ [1,n-1]
right(pₙ) = NULL

Constraint Analysis:

N ∈ [0,2000]:
- Enables O(N²) solutions but O(N) expected
- Recursion depth ≤ 2000 is generally safe
- Empty tree (N=0) must be handled
Node values ∈ [-100,100]:
- Values irrelevant to structure transformation
- No special handling needed for negative values
In-place requirement:
- Cannot create new nodes or external data structures
- Must manipulate existing node pointers only
Edge cases implied:
- Single node trees (Example 3)
- Left/right skewed trees
- Balanced vs unbalanced structures
- Trees with only left/right subtrees

2. Intuition Scaffolding

Real-World Metaphor: Imagine organizing a library where books (nodes) are arranged in sections (subtrees). The pre-order flattening is like taking all books off the shelves and lining them up on a single long table in the order you’d naturally browse them: start with current section, then left subsections, then right subsections.

Gaming Analogy: Think of a skill tree in an RPG where you want to “activate” all skills in optimal order. The flattening process is like creating a linear quest chain where you must complete all left-branch quests before moving to parallel right-branch quests, maintaining the natural progression order.

Math Analogy: This is equivalent to taking a partial order (tree hierarchy) and converting it to a total order (linear sequence) while preserving the pre-order relationship, similar to topological sorting but with specific ordering constraints.

Common Pitfalls:

Destroying original structure prematurely - If you break left pointers before processing left subtree, you lose access to critical parts of the tree
Stack overflow - Deep recursion on worst-case 2000-node trees
Assuming balanced trees - Solutions that work on balanced trees may fail on skewed ones
Forgetting to nullify left pointers - The problem explicitly requires left = null
Overcomplicating with extra storage - Using O(N) space when O(1) is possible

3. Approach Encyclopedia

Approach 1: Recursive Pre-Order with Storage

Pseudocode:
def flatten(root):
    if not root: return
    
    nodes = []  # O(N) storage
    preorder_collect(root, nodes)
    
    for i in range(len(nodes)-1):
        nodes[i].left = None
        nodes[i].right = nodes[i+1]
    nodes[-1].left = None
    nodes[-1].right = None

def preorder_collect(node, result):
    if not node: return
    result.append(node)
    preorder_collect(node.left, result)
    preorder_collect(node.right, result)

Complexity Proof:

Time: T(N) = O(N) for traversal + O(N) for rewiring = O(N)
Space: S(N) = O(N) for storage + O(h) recursion stack = O(N) worst case

Visualization:

Original:    1
            / \
           2   5
          / \   \
         3   4   6

Storage: [1, 2, 3, 4, 5, 6]

After: 1 → 2 → 3 → 4 → 5 → 6

Approach 2: Iterative Stack-Based

Pseudocode:
def flatten(root):
    if not root: return
    
    stack = [root]
    prev = None
    
    while stack:
        current = stack.pop()
        if prev:
            prev.left = None
            prev.right = current
        
        # Push right then left (LIFO)
        if current.right:
            stack.append(current.right)
        if current.left:
            stack.append(current.left)
            
        prev = current

Complexity Proof:

Time: T(N) = O(N) each node processed once
Space: S(N) = O(h) stack storage = O(N) worst-case skewed tree

Approach 3: Morris Traversal Style (O(1) Space)

Pseudocode:
def flatten(root):
    current = root
    while current:
        if current.left:
            # Find rightmost node in left subtree
            predecessor = current.left
            while predecessor.right:
                predecessor = predecessor.right
            
            # Rewire connections
            predecessor.right = current.right
            current.right = current.left
            current.left = None
        
        current = current.right

Complexity Proof:

Time: T(N) = O(N) - each node and predecessor traversed constant times
Space: S(N) = O(1) - only pointer manipulation, no recursion/stack

Visualization of O(1) Approach:

Step 0:     1
           / \
          2   5
         / \   \
        3   4   6

Step 1: Find predecessor of 1 (node 4)
        1
       / \
      2   5
     / \   \
    3   4   6
         \
          5  (predecessor.right = current.right)

Step 2: Rewire
    1
     \
      2
     / \
    3   4
         \
          5
           \
            6

4. Code Deep Dive

Optimal Solution (O(1) Space):

def flatten(root):
    """
    Flatten binary tree to linked list in-place using Morris traversal approach
    """
    current = root  # Tracks current node being processed
    
    while current:
        if current.left:  # Only process if left subtree exists
            # Find the rightmost node in the left subtree
            predecessor = current.left
            while predecessor.right:
                predecessor = predecessor.right
            
            # Rewire connections:
            # 1. Predecessor's right points to current's right subtree
            predecessor.right = current.right
            # 2. Current's right takes over left subtree
            current.right = current.left
            # 3. Current's left becomes null as required
            current.left = None
        
        # Move to next node in the flattened structure
        current = current.right

Line-by-Line Analysis:

Line 2-3: Documentation clarifying approach and space complexity
Line 5: current = root - Initialize traversal pointer
Line 7: while current: - Process until no more nodes
Line 8: if current.left: - Only restructure if left subtree exists
Line 10-12: Find predecessor - the rightmost node in left subtree
Line 15: predecessor.right = current.right - Attach current’s right subtree to predecessor
Line 17: current.right = current.left - Promote left subtree to right side
Line 19: current.left = None - Explicitly nullify left pointer
Line 22: current = current.right - Advance to next node in flattened structure

Edge Case Handling:

Empty tree (Example 2): while current: fails immediately, returns None
Single node (Example 3): if current.left: fails, loop terminates
Left-skewed tree: Predecessor finding works correctly for deep left chains
Right-skewed tree: if current.left: mostly fails, minimal restructuring needed

5. Complexity War Room

Hardware-Aware Analysis:

At N=2000 nodes, the O(1) space solution uses ~16KB for node pointers (assuming 8 bytes per pointer)
Fits comfortably in L1/L2 cache for modern processors
Pointer-chasing pattern may cause cache misses but N=2000 is manageable
Recursive solutions risk stack overflow at ~1000+ depth in some environments

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Recursive + Storage	O(N)	O(N)	9/10	✅ Good for explanation
Iterative Stack	O(N)	O(h)	8/10	✅ Demonstrates stack mastery
Morris O(1)	O(N)	O(1)	6/10	✅ Optimal for follow-up
Naive Recursive	O(N)	O(h)	10/10	❌ Fails constant space

Trade-off Analysis:

Recursive + Storage: Most intuitive but fails follow-up requirement
Iterative Stack: Good balance of readability and efficiency
Morris O(1): Meets all requirements but harder to conceptualize

6. Pro Mode Extras

Variants Section:

Flatten to Doubly Linked List: Maintain both left/right pointers for bidirectional traversal
Flatten in Post-Order: Reverse the restructuring logic to process children first
Flatten with Cycle Prevention: Add null checks for graphs that might contain cycles
LC 114 Follow-up: Exactly this problem - test O(1) space implementation
Multiple Flatten Operations: Consider persistence or undo capability

Interview Cheat Sheet:

First Mention: “I’ll solve this with O(N) time, discussing both O(N) and O(1) space approaches”
Whiteboard Strategy: Draw tree, show pointer manipulation step-by-step
Testing Protocol:
1. Empty tree
2. Single node
3. Left-skewed/right-skewed
4. Full binary tree
Common Gotchas:
- “Always nullify left pointers explicitly”
- “Handle predecessor finding carefully in left subtree”
- “Remember pre-order means current → left → right”
Optimization Path: “Start with recursive → discuss stack → final O(1) solution”

#114 - Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

Problem Description

Solution

1. Problem Deconstruction

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras