DSA AnimatorDSA animations
Flatten Binary Tree to Linked List LC #114 Medium DFS · In-place Mutation
Examples
Iterative Morris-style approach: For each node with a left child, find the rightmost node of the left subtree. Attach current's right subtree there, then swing the left subtree to the right. Repeat until no left children remain.
Tree Visualization
Right-Chain (Flattened So Far)
—
Operation
Waiting…
State Variables
curr
—
rightmost
—
curr.left?
—
step
—
Step Logic
—
✅
Flattened!
—
Problem Statement
Given the root of a binary tree, flatten the tree into a "linked list" in-place. The "linked list" should use TreeNode right pointers only, be in preorder traversal order, and all left pointers should be null.
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Preorder: 1→2→3→4→5→6 using right pointers only.
Input: root = [1,2,3]
Output: [1,null,2,null,3]
Preorder: 1→2→3
Input: root = [1]
Output: [1]
Single node — no change needed.
0 ≤ nodes ≤ 2000  |  −100 ≤ Node.val ≤ 100
Algorithm Steps
  • 1For each node curr with a left child:
  • 2Find rightmost node of left subtree
  • 3Attach: rightmost.right = curr.right
  • 4Move: curr.right = curr.left; curr.left = null
Complexity
Time
O(n²)
Space
O(1)
Why It Works
For each node, we find where its right subtree should go — at the rightmost of the left subtree. Then we swing the left subtree to the right position. This is O(n²) worst case but O(1) extra space, fully in-place.

The key insight: preorder = root, left, right. After stitching, the left subtree becomes the new right subtree, with the original right subtree appended at the end. No recursion or stack needed.

How to solve Flatten Binary Tree to Linked List

LeetCode 114 · Medium · Tree · Pattern: Preorder Rewiring

Why the obvious approach is slow

The simple way is to store the preorder in a list, and then relink the nodes one by one. That uses O(n) extra space. We can rewire the pointers directly, with O(1) extra space.

The key idea

Walk down the tree with a pointer called current. If current has a left subtree, find the rightmost node of that left subtree. That rightmost node is the last one in preorder before the right subtree, so attach the right subtree to it. Then move the left subtree to the right side, and set left to null. Move current to its right child, and repeat until current is null.

Remember

The rightmost node of the left subtree comes right before the right subtree. Splice there, move left to right, and keep walking right.

Run the animation above on your own input, or watch the 2:26 video explanation of Flatten Binary Tree to Linked List with a dry run and Java code.

More Tree problems