Watch 10 video solutions for Flatten Binary Tree to Linked List, a medium level problem involving Linked List, Stack, Tree. This walkthrough by take U forward has 232,578 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree, flatten the tree into a "linked list":
TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
Example 1:
Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [0] Output: [0]
Constraints:
[0, 2000].-100 <= Node.val <= 100Follow up: Can you flatten the tree in-place (with
O(1) extra space)?Problem Overview: Convert a binary tree into a linked list in-place following preorder traversal. After flattening, every node’s right pointer should point to the next node in preorder and every left pointer must be null.
Approach 1: Recursive Pre-order Traversal (O(n) time, O(h) space)
This approach uses Depth-First Search recursion to process the tree in preorder. You flatten the left and right subtrees first, then rewire pointers: attach the flattened left subtree to root.right, find its tail, and connect the original right subtree to that tail. The key insight is preserving the original right child before modifying pointers. Each node is visited once, giving O(n) time complexity, while recursion depth contributes O(h) space where h is tree height.
Approach 2: Iterative Pre-order Traversal with Stack (O(n) time, O(h) space)
This version simulates preorder traversal using an explicit stack. Push the root onto the stack, then repeatedly pop the current node. Push the right child first and the left child second so the left subtree is processed next. Rewire pointers so current.right points to the next node in the stack and set current.left = null. The structure gradually becomes a right-skewed chain that behaves like a linked list. Time complexity is O(n) since each node is processed once, and the stack requires O(h) space.
Approach 3: Morris-style In-place Traversal (O(n) time, O(1) space)
An optimized approach avoids recursion and stacks by rewiring the tree similarly to Morris traversal. For each node that has a left child, locate the rightmost node in its left subtree (the preorder predecessor). Connect that node’s right pointer to the current node’s original right subtree, then move the left subtree to the right and set left = null. Continue walking through the right pointers. Each edge is visited a constant number of times, giving O(n) time and O(1) extra space.
Recommended for interviews: The recursive preorder approach is the most commonly expected solution because it clearly demonstrates understanding of tree restructuring and binary tree traversal. The iterative stack version is also interview-friendly since it avoids recursion and shows explicit control of traversal order. The Morris-style method is optimal for space but less frequently expected unless the interviewer specifically asks for constant space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Pre-order Traversal | O(n) | O(h) | Standard interview solution; easy to reason about with DFS recursion |
| Iterative Pre-order Traversal (Stack) | O(n) | O(h) | When recursion is restricted or you want explicit traversal control |
| Morris-style In-place Traversal | O(n) | O(1) | Memory-constrained scenarios requiring constant extra space |