Skip to main content

114 - Flatten Binary Tree to Linked List

Difficulty: Medium | Pattern: Tree DFS / Morris Traversal | Company tags: Microsoft, Amazon, Apple, Bloomberg

Problem Statement​

Given the root of a binary tree, flatten the tree into a linked list in-place.

The linked list should be in the same order as a pre-order traversal of the binary tree. Use TreeNode.right pointers; set all left pointers to None.

Example:

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

Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 (using right pointers)

Approach: Iterative (O(n), O(1) extra space)​

Key insight: For each node with a left child, find the rightmost node of the left subtree (the pre-order predecessor). Attach the right subtree there, then move the left subtree to the right.

def flatten(root) -> None:
    curr = root
    while curr:
        if curr.left:
            # Find rightmost node of left subtree
            rightmost = curr.left
            while rightmost.right:
                rightmost = rightmost.right
            
            # Attach right subtree to rightmost of left subtree
            rightmost.right = curr.right
            
            # Move left subtree to right
            curr.right = curr.left
            curr.left = None
        
        curr = curr.right

Algorithm Flow​

Recursive Approach (Post-Order)​

def flatten(root) -> None:
    def helper(node):
        if not node:
            return None  # return tail
        if not node.left and not node.right:
            return node  # leaf is its own tail
        
        left_tail = helper(node.left)
        right_tail = helper(node.right)
        
        if left_tail:
            left_tail.right = node.right
            node.right = node.left
            node.left = None
        
        return right_tail or left_tail
    
    helper(root)

Dry Run (Iterative)​

    1           Step 1: curr=1, left=2, rightmost of 2's left subtree = 4
   / \           → 4.right = 5; 1.right = 2; 1.left = None
  2   5    →    1→2→3; 2.right=4→5→6
 / \   \
3   4   6

After step 1: 1.right=2, 1.left=None Tree: 1→[2→[3, 4→[5→6]]]

Next curr=2: left=3, rightmost of 3 = 3 (no right); 3.right=4; 2.right=3; 2.left=None

Continue until all left pointers are None.

Final: 1→2→3→4→5→6 ✓

Edge Cases​

  • Empty tree → do nothing
  • Only right children → already flattened, no left to process
  • Only left children → each iteration moves left to right

Complexity​

ApproachTimeSpace
Iterative (find rightmost)O(n) amortizedO(1)
RecursiveO(n)O(h) stack

Key Terms​

TermDefinition
Pre-order traversalVisit order: node, then left subtree, then right subtree.
In-placeModifying the structure without allocating a new tree/list.
Morris traversalO(1)-space traversal technique that temporarily uses null right-child pointers as threads back to predecessors.
PredecessorThe rightmost node of a subtree, i.e., the last node visited before moving to the next subtree in pre-order.

FAQ​

Q: Why does finding the "rightmost node of the left subtree" work? A: In pre-order, the entire left subtree is visited before the right subtree. The rightmost node of the left subtree is the last node processed before the original right subtree should appear, so linking it there preserves pre-order.

Q: Can this be solved without extra space? A: Yes — the iterative approach uses O(1) extra space by threading pointers directly on the existing tree nodes (a Morris-traversal-style trick).

Q: What happens if the tree has only right children? A: The tree is already in flattened form; the loop just walks down curr.right without any rewiring.

Q: How does the recursive approach differ in what it returns? A: It returns the "tail" of the already-flattened subtree so the caller can attach the next subtree at the correct end in O(1) per call.

Q: Is this problem asked with a "return the head" variant? A: No — since it modifies in-place and root remains the head, but interviewers sometimes ask you to also return a new list, in which case cloning is required first.

Quick Revision​

  • Goal: reorder tree into a right-skewed "linked list" following pre-order.
  • Iterative: find rightmost node of curr.left, attach curr.right there, move left subtree to right.
  • Recursive: post-order DFS returning the tail of each flattened subtree.
  • Time: O(n); Space: O(1) iterative, O(h) recursive (call stack).
  • No left pointers remain — all set to None.
  • Edge cases: empty tree (no-op), single node, right-skewed tree (already done).
  • Mentally simulate with a 3-node tree before coding to catch pointer-order bugs.