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
The 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. The key insight is that preorder traversal order can be captured by a simple recursive function that appends nodes to a list. Then, rewiring pointers in a single pass over this list produces the flattened tree.
Optimal Approach
Perform 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. This approach is straightforward, easy to implement, and clearly separates traversal from pointer rewiring, though it uses O(n) space.
Time
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
| 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 |
Objective
To iterate through the collected nodes and set each node's left child to null and right child to the next node in preorder.
Key Insight
By iterating through the list of nodes, the algorithm can systematically reassign pointers without worrying about traversal state. Setting left to null ensures the linked list property, and linking right to the next node preserves preorder sequence. This step finalizes the in-place transformation.
Interview Quick-Check
Core Logic
The loop rewires each node's left pointer to null and right pointer to the next node, effectively creating a singly linked list following preorder.
State & Boundaries
The loop runs from the second node to the end, using the previous node to update pointers, ensuring no node is skipped.
Common Pitfalls & Bugs
Failing to set left to null would leave the original tree structure partially intact, violating the problem's requirements.
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.
if not node:Check if the current node is null.
The base case halts recursion when a null child is encountered, preventing invalid access and ensuring correct termination at leaf boundaries.
preorder(node.right)Traverse the right subtree.
After completing the left subtree, the traversal continues into the right subtree to complete the preorder pattern of root → left → right.
preorder(root)Start the preorder traversal from the root.
Initiating traversal from the root populates the list with every node in preorder order, which directly determines the final flattened sequence.
nodes = []Initialize a list to store nodes in preorder order.
This list captures nodes in exact preorder sequence. Separating traversal from pointer rewiring simplifies reasoning and avoids mutating the tree during recursion.
preorder(node.left)Traverse the left subtree.
Recursing into the left subtree immediately after the root preserves the preorder invariant of visiting left children before right children.
for i in range(1, len(nodes)):Iterate through nodes beginning with the second preorder element.
Iterating through the preorder list allows the algorithm to reconnect nodes sequentially into a right-skewed linked list.
def preorder(node):Define a helper function to perform preorder traversal.
Encapsulating traversal in a helper isolates the recursive preorder logic from the flattening step, making the algorithm easier to understand.
returnStop recursion when the node is null.
Returning immediately prevents further recursion on nonexistent nodes.
prev = nodes[i-1]Identify the previous node in preorder.
The previous node is the one whose pointers will be updated to link to the next node in the preorder sequence.
curr = nodes[i]Identify the current node in preorder.
The current node becomes the next element in the flattened linked list.
Test Your Understanding
Why does collecting nodes in preorder first simplify the flattening process compared to modifying pointers during traversal?
Collecting nodes in preorder first separates traversal logic from pointer manipulation, avoiding complex pointer state management during recursion and ensuring the flattened list follows the exact preorder sequence.
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