Flatten Binary Tree to Linked List
Problem
left pointer becomes null and its right pointer
points to the next node. The chain must list the nodes in the tree's pre-order
(node, then left subtree, then right subtree). Return nothing; modify
root directly.root = [4,2,6,1,3]Output[4,null,2,null,1,null,3,null,6]root = [7,null,8]Output[7,null,8]root = []Output[]0 ≤ nodes ≤ 2000 · -100 ≤ Node.val ≤ 100 · Follow-up: O(1) extra space.
Try it yourself
class Solution {
public void flatten(TreeNode root) {
}
}
cur.right there, move the left subtree to the right, and step
forward — no stack or recursion needed.Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.
Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.
Open the Tree DFS guide →Approaches
Brute ForcePre-order List, then Relink
O(n)Space O(n)Record all nodes in pre-order into a list, then walk the list and set
left = null and right = next node for each one. The
links are rewritten only after the traversal, so nothing is lost while
reading.
public void flatten(TreeNode root) { List<TreeNode> order = new ArrayList<>(); preorder(root, order); for (int i = 0; i < order.size(); i++) { 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); }
Simple and safe, but stores every node — fails the O(1)-space follow-up.
BetterReverse Pre-order with a prev Pointer
O(n)Space O(h)Visit nodes in the exact reverse of pre-order (right, left, node). When a
node is reached, prev is the node that must follow it in the chain,
so set node.right = prev, clear node.left, and make the
node the new prev. Its children were already processed, so
overwriting their links is safe.
private TreeNode prev; public void flatten(TreeNode root) { prev = null; build(root); } private void build(TreeNode node) { if (node == null) return; build(node.right); build(node.left); node.right = prev; // prev = next node in pre-order node.left = null; prev = node; }
No list, but the recursion still uses O(h) stack — O(n) on a skewed tree.
OptimalIterative Splicing (Morris-style)
O(n)Space O(1)Walk down the right pointers with cur. Whenever
cur has a left child, find the rightmost node of that left subtree,
attach cur.right to it, then move the left subtree into
cur.right. Each node is scanned as a “rightmost”
candidate only a bounded number of times, so the total work is linear.
public void flatten(TreeNode root) { TreeNode cur = root; while (cur != null) { if (cur.left != null) { TreeNode tail = cur.left; while (tail.right != null) tail = tail.right; // end of left part tail.right = cur.right; cur.right = cur.left; cur.left = null; } cur = cur.right; } }
Linear time with constant extra memory — meets the follow-up.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Pre-order List, then Relink | O(n) | O(n) |
| Better | Reverse Pre-order with a prev Pointer | O(n) | O(h) |
| Optimal | Iterative Splicing (Morris-style) | O(n) | O(1) |
- Forgetting to set
left = null— the result must be a pure right-chain. - Overwriting
cur.rightbefore saving it; the old right subtree is lost. - In the recursive version, processing left before right breaks the reverse-pre-order invariant.
- Start with the list approach, then ask whether O(1) extra space is required.
- Explain the splice with a 3-node picture: left subtree goes between cur and its old right.
- Argue the O(n) bound: each edge is walked by the rightmost search at most once.