#114 Flatten Binary Tree to Linked List
the problem
In plain words
Rewire a binary tree in place into a "linked list" made of the same TreeNode objects: each node's right pointer goes to the next node in preorder, and every left pointer becomes null. The method returns nothing.
in root = [1,2,5,3,4,null,6]
out [1,null,2,null,3,null,4,null,5,null,6]
Preorder is 1, 2, 3, 4, 5, 6.
in root = []
out []
in root = [0]
out [0]
- 0 ≤ number of nodes ≤ 2000
- -100 ≤ Node.val ≤ 100
- Follow-up: O(1) extra space
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternIn-place linked-list rewiringTree DFS (bottom-up)
In preorder, the whole left subtree comes right after a node, and the right subtree comes after everything in the left. So hang the right subtree off the rightmost node of the left subtree, move the left subtree to the right, and walk on.
solutions
From brute force to optimal
Collect the nodes in preorder into a list, then point each one at the next.
- Preorder DFS into a List<TreeNode>.
- For each i: left = null, right = list[i + 1] (null for the last).
One traversal plus one pass over the list.
The list holds every node.
class Solution { public void flatten(TreeNode root) { List<TreeNode> order = new ArrayList<>(); preorder(root, order); // 1) remember the final order for (int i = 0; i < order.size(); i++) { // 2) relink: each node points to the next TreeNode node = order.get(i); node.left = null; node.right = i + 1 < order.size() ? order.get(i + 1) : null; } } private void preorder(TreeNode node, List<TreeNode> order) { if (node == null) return; order.add(node); preorder(node.left, order); preorder(node.right, order); }}Visit right, then left, then the node — preorder backwards. The node visited just before is exactly this node's successor.
- link(null) → return.
- link(right); link(left).
- node.right = prev; node.left = null; prev = node.
Each node is visited once.
Recursion stack only — no list.
class Solution { private TreeNode prev; // the node that must come right after the current one public void flatten(TreeNode root) { prev = null; link(root); } /** Visits right, left, then the node: preorder backwards, so prev is always the node's successor. */ private void link(TreeNode node) { if (node == null) return; link(node.right); link(node.left); node.right = prev; node.left = null; prev = node; }}Walk down the right pointers. Whenever a node has a left subtree, splice it in between the node and its right subtree.
- If node.left != null: tail = rightmost node of node.left.
- tail.right = node.right; node.right = node.left; node.left = null.
- node = node.right; repeat until null.
The main loop takes n steps, and a node is walked by a rightmost-search at most once — after the splice it sits on the right chain, which the loop only passes.
A few pointers — no recursion, no list.
class Solution { public void flatten(TreeNode root) { TreeNode node = root; while (node != null) { if (node.left != null) { TreeNode tail = node.left; // rightmost node of the left subtree while (tail.right != null) tail = tail.right; tail.right = node.right; // the right subtree hangs off it node.right = node.left; // the left subtree moves to the right node.left = null; } node = node.right; // next node in preorder } }}in the room
How to say it in the interview
talk track
- Clarify: in place, preorder order, every left pointer null, nothing returned.
- Give the list version first (easy to trust), then the prev-pointer recursion, then the O(1)-space splice for the follow-up.
- Dry-run the splice on [1,2,5,3,4,null,6]: at 1, the rightmost node of the left subtree is 4; 5 hangs under 4, and 2's subtree moves to 1's right.
traps
- Setting node.right = node.left but forgetting node.left = null — LeetCode checks the left pointers too.
- Overwriting node.right before saving it: the right subtree is lost. Splice it under the left subtree first.
- A prev pointer in plain preorder (node, left, right): you overwrite node.right before you visit it. Go right, left, node instead.
what they ask next
Follow-ups
Flatten a BST into a sorted doubly linked list (LC 426)?
An inorder walk with a prev pointer: prev.right = node, node.left = prev. LC 426 also links the last node back to the first.
Why is the O(1) version still O(n)?
A node is searched as the rightmost of some left subtree at most once; after the splice it lies on the right chain, which the main loop just walks.
before you submit
Edge cases to test
- Empty tree → nothing to do.
- Only left children: a left chain becomes a right chain.
- Already flat (only right children) → unchanged.
practise next
Similar problems
- #206Reverse Linked ListEasyin Linked Lists
- #117Populating Next Right Pointers in Each Node IIMediumin Traversals
- #226Invert Binary TreeEasyin Tree Recursion