Flatten Binary Tree to Linked List
Problem
Given the root of a binary tree, flatten the tree into a linked list in-place following the preorder traversal order, where each node's right child points to the next node in preorder and left child is always null.
- The number of nodes in the tree is in the range [0, 2000]
- −100 ≤ Node.val ≤ 100
Example
root = [1,2,5,3,4,null,6][1,null,2,null,3,null,4,null,5,null,6]The preorder traversal of the tree is [1,2,3,4,5,6]. The algorithm first collects nodes in preorder into a list. Then, it iterates through the list, setting each node's left child to null and right child to the next node in the preorder sequence. This results in a right-skewed linked list matching preorder.
Approach
Straightforward Solution
A brute-force approach would repeatedly rearrange pointers during traversal, which is complex and error-prone. Alternatively, one could perform a preorder traversal, store nodes in a list, then iterate through the list to rewire pointers. This uses O(n) extra space.
Core Observation
Preorder traversal visits nodes in the order: root, left subtree, right subtree. Flattening the tree into a linked list following preorder means rearranging pointers so that the right child points to the next node in this sequence and left child is null.
Path to Optimal
PreviewThe problem can be solved in-place using a recursive approach that modifies pointers during traversal, but this solution uses extra space to store nodes in preorder…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewPerform a preorder traversal to collect nodes in a list. Then iterate through the list, setting each node's left child to null and right child to the next node in the list…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm visits each node exactly twice: once during preorder traversal to collect nodes, and once during the rewiring pass. Both passes are linear in the number of nodes.
Space
O(n)
The auxiliary space is used to store the list of nodes in preorder. This list grows linearly with the number of nodes. The in-place pointer rewiring does not use additional space.
Pattern Spotlight
DFS (Preorder Traversal with Postprocessing)
When a problem requires rearranging a tree according to a traversal order, first collect nodes in that order via DFS, then perform a separate pass to rewire pointers, simplifying in-place transformations.
Solution
| 1 | class Solution: |
| 2 | def flatten(self, root: Optional[TreeNode]) -> None: |
| 3 | nodes = [] |
| 4 | |
| 5 | def preorder(node): |
| 6 | if not node: |
| 7 | return |
| 8 | nodes.append(node) |
| 9 | preorder(node.left) |
| 10 | preorder(node.right) |
| 11 | |
| 12 | preorder(root) |
| 13 | |
| 14 | for i in range(1, len(nodes)): |
| 15 | prev = nodes[i-1] |
| 16 | curr = nodes[i] |
| 17 | prev.left = None |
| 18 | prev.right = curr |
Step-by-Step Solution
Collect Nodes in Preorder Traversal
| 3 | nodes = [] |
| 5 | def preorder(node): |
| 6 | if not node: |
| 7 | return |
| 8 | nodes.append(node) |
| 9 | preorder(node.left) |
| 10 | preorder(node.right) |
| 12 | preorder(root) |
Objective
To traverse the tree in preorder and collect all nodes in a list preserving traversal order.
Key Insight
Preorder traversal visits the root before its subtrees, so appending nodes to a list during this traversal captures the exact order needed for flattening. This decouples traversal from pointer rewiring, making the algorithm easier to reason about and implement.
Interview Quick-Check
Core Logic
The recursive preorder function visits each node, appends it to the list, then recursively visits left and right children, ensuring the list reflects preorder.
State & Boundaries
The base case returns immediately when a null node is encountered, preventing invalid accesses.
Common Pitfalls & Bugs
Forgetting to append the current node before recursive calls would produce an incorrect traversal order.
Rewire Pointers to Form Flattened Linked List
To iterate through the collected nodes and set each node's left child to null and right child to the next node in preorder.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
nodes.append(node)Record the current node in the preorder sequence.
Appending the node before visiting its children enforces preorder semantics: process the root before its subtrees.
prev.left = NoneRemove the previous node's left child.
Setting the left pointer to null enforces the final linked list structure where all nodes are connected exclusively through right pointers.
prev.right = currConnect the previous node to the current node via the right pointer.
Redirecting the right pointer links the previous node to the next node in preorder, constructing the flattened linked list.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why does collecting nodes in preorder first simplify the flattening process compared to modifying pointers during traversal?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Flatten Binary Tree to Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Flatten Binary Tree to Linked List drill