Flatten Binary Tree to Linked List

Flattening a binary tree into a linked list is one of the most commonly tested tree-to-list conversion problems. The idea is deceptively simple — take a tree, rearrange its pointers so it becomes a singly linked list — but the implementation reveals deep insights about traversal order, pointer manipulation, and in-place algorithms.

In this article we’ll tackle the classic LeetCode 114 problem and then extend the idea to BST-to-DLL conversion.

---

Problem Statement: Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a “linked list” using the right pointer. After flattening:

• Every node’s left child should be None
• Every node’s right child should point to the next node in preorder traversal
• The list should use the same TreeNode objects — no new nodes

Input:        Output (as right-linked list):
     1              1
    / \               \
   2   5               2
  / \   \               \
 3   4   6               3
                          \
                           4
                            \
                             5
                              \
                               6

The preorder of the tree is [1, 2, 3, 4, 5, 6], and that’s exactly the order of the resulting list.

---

TreeNode Definition

All solutions in this article use the same node class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

---

Approach 1: Preorder Traversal with a List

The simplest way is to collect all nodes in preorder, then rewire pointers.

def flatten(root):
    """Flatten binary tree to linked list using preorder collection."""
    if not root:
        return

    # Step 1: Collect nodes in preorder
    nodes = []

    def preorder(node):
        if not node:
            return
        nodes.append(node)
        preorder(node.left)
        preorder(node.right)

    preorder(root)

    # Step 2: Rewire pointers
    for i in range(len(nodes) - 1):
        nodes[i].left = None
        nodes[i].right = nodes[i + 1]

    # Last node
    nodes[-1].left = None
    nodes[-1].right = None

Complexity

Metric	Value
Time	O(n) — visit every node once
Space	O(n) — store all nodes in a list

This works but uses O(n) extra space. Can we do better?

---

Approach 2: Recursive Reverse Postorder

Here’s the elegant trick: process the tree in reverse preorder (right, left, root). We maintain a global prev pointer that tracks the previously processed node.

def flatten(root):
    """Flatten using reverse postorder (right-left-root)."""
    prev = None

    def dfs(node):
        nonlocal prev
        if not node:
            return

        # Process right subtree first
        dfs(node.right)
        # Then left subtree
        dfs(node.left)

        # Now wire this node
        node.right = prev
        node.left = None
        prev = node

    dfs(root)

Why reverse postorder works

If preorder is [1, 2, 3, 4, 5, 6], then reverse preorder is [6, 5, 4, 3, 2, 1]. By processing in this order, when we reach node 5, prev is already 6. We set 5.right = 6, and the chain builds backward.

Complexity

Metric	Value
Time	O(n)
Space	O(h) — recursion stack, where h is tree height

---

Approach 3: Iterative with Stack

We can simulate preorder using an explicit stack to avoid recursion.

def flatten(root):
    """Flatten using iterative preorder with a stack."""
    if not root:
        return

    stack = [root]

    while stack:
        node = stack.pop()

        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

        # Wire to next node in stack (next in preorder)
        if stack:
            node.right = stack[-1]
        node.left = None

Complexity

Metric	Value
Time	O(n)
Space	O(h) — stack holds at most O(h) nodes

---

Approach 4: Morris Traversal — O(1) Space

The Morris approach achieves O(1) extra space by using the tree’s own right pointers temporarily. The key idea: for each node, find the rightmost node of its left subtree (the preorder predecessor of the right child) and link it to the current node’s right child.

def flatten(root):
    """Flatten using Morris-style threading — O(1) space."""
    current = root

    while current:
        if current.left:
            # Find the rightmost node of the left subtree
            runner = current.left
            while runner.right:
                runner = runner.right

            # Thread: connect rightmost of left subtree to current's right
            runner.right = current.right

            # Move left subtree to right
            current.right = current.left
            current.left = None

        # Move to the next node
        current = current.right

Step-by-step example

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

Step 1: current=1, left subtree rightmost is 4
        Connect 4.right = 5, move left to right

             1
              \
               2
              / \
             3   4
                  \
                   5
                    \
                     6

Step 2: current=2, left subtree rightmost is 3
        Connect 3.right = 4, move left to right

             1
              \
               2
                \
                 3
                  \
                   4
                    \
                     5
                      \
                       6

Done! All nodes linked via right pointers.

Complexity

Metric	Value
Time	O(n) — each edge is visited at most twice
Space	O(1) — no extra data structures

This is the optimal solution.

---

BST to Sorted Doubly Linked List

A related and equally important problem: convert a BST into a sorted circular doubly linked list in-place. Each node’s left becomes prev and right becomes next.

Input BST:        Output DLL:
      4           1 <-> 2 <-> 3 <-> 4 <-> 5
     / \          ^                       |
    2   5         |_______________________|
   / \            (circular)
  1   3

Solution: Inorder Traversal with Pointer Wiring

def bst_to_dll(root):
    """Convert BST to sorted circular doubly linked list."""
    if not root:
        return None

    first = None  # Head of the DLL
    last = None   # Tail — most recently visited node

    def inorder(node):
        nonlocal first, last

        if not node:
            return

        inorder(node.left)

        # Process current node
        if last:
            # Wire last <-> current
            last.right = node
            node.left = last
        else:
            # First node in inorder — this is the head
            first = node

        last = node

        inorder(node.right)

    inorder(root)

    # Make it circular
    first.left = last
    last.right = first

    return first

Verification

def print_dll(head, count=10):
    """Print the circular DLL forward."""
    if not head:
        print("Empty")
        return

    node = head
    result = []
    for _ in range(count):
        result.append(str(node.val))
        node = node.right
        if node == head:
            break
    print(" <-> ".join(result))

# Build BST
root = TreeNode(4)
root.left = TreeNode(2, TreeNode(1), TreeNode(3))
root.right = TreeNode(5)

head = bst_to_dll(root)
print_dll(head)
# Output: 1 <-> 2 <-> 3 <-> 4 <-> 5

Complexity

Metric	Value
Time	O(n) — standard inorder
Space	O(h) — recursion stack

---

Flatten to Linked List Using Inorder (Variation)

Sometimes you need the list in inorder instead of preorder. The approach is similar but uses inorder traversal:

def flatten_inorder(root):
    """Flatten binary tree to right-linked list in inorder."""
    prev = None

    def inorder(node):
        nonlocal prev
        if not node:
            return

        inorder(node.left)

        # Wire previous node to current
        if prev:
            prev.right = node
        node.left = None
        prev = node

        inorder(node.right)

    # We need a dummy to track the new head
    dummy = TreeNode(-1)
    prev = dummy
    inorder(root)

    return dummy.right

---

Flatten N-ary Tree to Linked List

For completeness, here’s the extension to an N-ary tree where each node has a list of children:

class NaryNode:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children or []

def flatten_nary(root):
    """Flatten N-ary tree to a singly linked list (preorder)."""
    if not root:
        return None

    # Collect in preorder
    result = []

    def preorder(node):
        if not node:
            return
        result.append(node)
        for child in node.children:
            preorder(child)

    preorder(root)

    # Rewire using a 'next' pointer (or reuse children[0])
    for i in range(len(result) - 1):
        result[i].children = []
        result[i].next = result[i + 1]
    result[-1].children = []
    result[-1].next = None

    return result[0]

---

Comparison of Approaches

Approach	Time	Space	Modifies in-place?
Preorder + list	O(n)	O(n)	Yes, after collection
Reverse postorder	O(n)	O(h)	Yes
Iterative stack	O(n)	O(h)	Yes
Morris traversal	O(n)	O(1)	Yes
BST to DLL	O(n)	O(h)	Yes

The Morris approach is optimal for interviews when the interviewer asks “can you do it in O(1) space?”

---

Common Mistakes

1. Forgetting to set node.left = None — if you only rewire right, traversal loops can occur because left still points to a subtree that’s now part of the right chain.

2. Losing the right subtree — when you move the left subtree to the right, you must save the original right child first (or thread it properly).

3. Off-by-one in the list approach — don’t forget to handle the last node separately (set both left and right to None).

---

Practice Problems

Problem	Platform	Difficulty
Flatten Binary Tree to Linked List	LeetCode 114	Medium
Convert Binary Search Tree to Sorted Doubly Linked List	LeetCode 426	Medium
Flatten a Multilevel Doubly Linked List	LeetCode 430	Medium
Flatten Nested List Iterator	LeetCode 341	Medium
Increasing Order Search Tree	LeetCode 897	Easy

---

Key Takeaways

• Preorder threading is the heart of flatten-to-linked-list problems. Understand how reverse postorder builds the chain backward.
• Morris traversal gives O(1) space by temporarily using right pointers as threads — the interviewer favorite.
• BST to DLL uses inorder and is a common follow-up. Remember to make the list circular at the end.
• Always null out the left pointer after rewiring to avoid cycles.
• These problems train your ability to manipulate tree pointers in-place — a skill that transfers to many advanced tree problems.