114. Flatten Binary Tree to Linked List¶

Edited by Charles

Medium · Python · Binary Tree

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

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

Original study notes follow, including intermediate snippets and earlier attempts.

Problem¶

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

The flattened tree should satisfy:

Every node's left child is None
Every node's right child points to the next node

The order of nodes should follow preorder traversal:

root → left → right

Example¶

Given:

After flattening:

Equivalent to:

1 → 2 → 3 → 4 → 5 → 6

The main idea is:

First recursively flatten the left subtree and the right subtree, then connect them together.

For every node:

        node
       /    \
    left    right

we want to transform it into:

node
  \
  left
    \
    ...
      \
      right

So the processing order is:

flatten(left)
flatten(right)
process current node

This is a postorder-style recursion.

For the current node:

self.flatten(root.left)
self.flatten(root.right)

After these two recursive calls, we can assume that both subtrees have already been flattened.

For example:

After recursively flattening the left subtree:

After recursively flattening the right subtree:

5
 \
  6

Now we only need to connect these two flattened lists.

Before changing the pointers, save them:

left = root.left
right = root.right

We need to do this because we are about to modify:

root.left
root.right

If we do not save the original right subtree, we may lose it.

The flattened tree must have:

left child = None

So:

root.left = None

Then move the flattened left subtree to the right:

root.right = left

For example:

At this moment, the original right subtree 5 is temporarily disconnected, but we already saved it in:

right

Now we need to attach the original right subtree after the flattened left subtree.

Suppose the left subtree has already become:

We need to find the last node:

So:

cur = root

while cur.right:
    cur = cur.right

After the loop, cur points to the last node of the current right chain.

Now connect:

cur.right = right

For example:

Before:

1
 \
  2
   \
    3
     \
      4

right:

5
 \
  6

After:

This gives the correct preorder order:

root → left subtree → right subtree

Preorder traversal is:

root → left → right

After flattening, we want:

root
  \
  flattened left subtree
        \
        flattened right subtree

So the right pointer chain becomes exactly:

root → left subtree → right subtree

which is preorder order.

Consider:

Process Node `2`¶

Its left subtree is:

Its right subtree is:

After flattening both:

and:

Move left to right:

2
 \
  3

Then attach the original right subtree:

So the subtree rooted at 2 is finished.

Process Node `5`¶

Node 5 has only a right child:

5
 \
  6

So it is already in the correct form.

Process Node `1`¶

Now the left subtree is:

and the right subtree is:

5
 \
  6

Move the left subtree to the right:

Then attach the original right subtree:

Done.

For every node:

        node
       /    \
    left    right

First:

flatten(left)
flatten(right)

Then:

save left and right

Then:

root.left = None
root.right = left

Then find the end of the right chain:

root → flattened left → ... → tail

Finally:

tail.right = original right

We write:

left = root.left
right = root.right

before changing the pointers.

Because after:

root.right = left

the original:

root.right

would be overwritten.

So we must save it first:

right = root.right

Otherwise, the original right subtree would be lost.

Time Complexity¶

The recursive traversal visits every node.

However, for every node, we may also search down the right chain:

while cur.right:
    cur = cur.right

In the worst case, this repeated search can make the total time complexity:

O(n²)

For example, when the tree is highly unbalanced.

Space Complexity¶

The recursion stack depends on the height of the tree:

O(h)

For a balanced tree:

O(log n)

For a completely skewed tree:

O(n)

The recursive idea is:

1. Flatten left subtree
2. Flatten right subtree
3. Move left subtree to the right
4. Find the end of the flattened left subtree
5. Attach the original right subtree

The structure changes from:

        node
       /    \
    left    right

to:

node
  \
  left
    \
    ...
      \
      right

The most important thing to remember is:

Preorder order:
root → left → right

So after recursively flattening both subtrees, we simply connect them as:

root → flattened left → flattened right

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 10, 2026

Python solution¶

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return

        self.flatten(root.left)
        self.flatten(root.right)

        left = root.left
        right = root.right

        root.left = None
        root.right = left

        cur = root

        while cur.right:
            cur = cur.right

        cur.right = right

Back to Bonus Binary Tree · All Algorithm notes

114. Flatten Binary Tree to Linked List¶

Problem¶

Example¶

Process Node 2¶

Process Node 5¶

Process Node 1¶

Time Complexity¶

Space Complexity¶

Python solution¶

Process Node `2`¶

Process Node `5`¶

Process Node `1`¶