← DSA Atlas
Dedicated problem page · #114

Flatten Binary Tree to Linked List

MediumTrees and Binary Search TreesIn-place preorder threadingMorris-style pointer rewiring
Solve on LeetCode ↗
114
MediumTrees and Binary Search TreesMorris-style pointer rewiringIn-place preorder threading

Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten it in place into a linked list. The linked list uses the same TreeNode class where each node's right child points to the next node in preorder and each node's left child is set to null.

Open official problem prompt ↗
In plain English

Rearrange the tree in place so following right pointers visits nodes in preorder and no left pointers remain.

Picture it like this

Think of each left branch as a detour that must be spliced into the main road: you connect the end of the detour back to where the main road continued, then reroute the main road through the detour.

Example
Input
root = [1,2,5,3,4,null,6]
Output
[1,null,2,null,3,null,4,null,5,null,6]
Why
Preorder is 1,2,3,4,5,6; each becomes the right child of the previous with all left children nulled.
Constraints
The number of nodes is in the range [0, 2000]-100 <= Node.val <= 100
Pattern lesson

See the pattern, then code

In-place preorder threading
Recognition clue

You must rearrange the existing tree into preorder order using the right pointers, ideally without extra storage — that points to rewiring left subtrees onto the right spine.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. For each node that has a left subtree, splice that whole left subtree between the node and its current right subtree by attaching the old right subtree to the rightmost node of the left subtree.

New words, made simpleKnow these before the algorithm
Preorder
Visit node, then left subtree, then right subtree
Rightmost node
The node reached by following right pointers to the end of a subtree
In place
Rewire existing nodes without allocating new ones
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Preorder list then relink

Simple but uses O(n) extra memory for the node list.

Collect nodes by preorder traversal into an array, then set each node's right to the next.

Time O(n)Space O(n)
Best choiceMorris-style splicing

No extra memory and each edge is touched a constant number of times.

For each node with a left subtree, thread its old right subtree onto the left subtree's rightmost node, then swap left to right.

Time O(n)Space O(1)
The rule we keep true

Invariant

After processing node cur, everything already on the right spine up to and including cur is in correct preorder and has no left children.

Why this is correct

Reasoning

Splicing the entire left subtree before the old right subtree reproduces preorder locally (node, then all of left, then all of right). Because the old right subtree is reattached at the left subtree's rightmost tip, no nodes are lost, and repeating down the spine flattens the whole tree.

The algorithm in three movesSay these aloud before coding
1Walk a pointer cur down the evolving right spine

cur=1: left=2, rightmost of left=4 -> 4.right=5

2If cur has a left child, find the rightmost node of that left subtree

1.right=2, 1.left=None

3Attach cur.right to that rightmost node

cur=2 ... continue down spine

4Move cur.left to cur.right and set cur.left to null, then advance cur

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
43
54
65
1 · Readleft subtree rooted at 2
2 · AskWhere does the old right (5) attach?
3 · Update staterightmost of {2,3,4} is 4
4 · Result4.right=5; 1.right=2; 1.left=None
Key takeaway

The final right-only spine in preorder: 1->2->3->4->5->6.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-5Walk the spine

    cur advances along the right pointers as the list forms.

  2. 2
    Lines 6-9Find reattach point

    The rightmost node of the left subtree is where the detached right subtree must hang.

  3. 3
    Lines 10-12Splice and null the left

    Move the left subtree onto the right and clear the left pointer as the spec requires.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty tree — loop body never runs
  • A node with only a right child needs no splice, just advance
  • A left-heavy tree (all left children) becomes a straight right spine
  • A single node is already flattened
!

Common beginner mistakes

  • Overwriting cur.right before saving it, losing the old right subtree
  • Forgetting to set cur.left to null, leaving stray left pointers
  • Advancing cur to cur.left instead of cur.right after the splice
Check your understanding

Why attach the old right subtree to the rightmost node of the left subtree rather than to its root?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split