Flatten Binary Tree to Linked ListLC #114MediumDFS · 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.