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: You receive the root of a binary tree and must transform it into a linked list in-place. The linked list should follow the same order as a preorder traversal (root → left → right). Every node’s left pointer becomes null, and the right pointer acts as the next pointer in the list.
Approach 1: Recursive Pre-order Traversal (O(n) time, O(h) space)
This approach uses a classic Depth-First Search recursion that processes nodes in preorder. Maintain a reference to the previously visited node. During traversal, set prev.right = current and prev.left = null to build the linked structure incrementally. The key insight is to traverse the right subtree after the left while rewiring pointers as you go. Time complexity is O(n) because each node is visited once. Space complexity is O(h), where h is the tree height due to the recursion stack.
Approach 2: Iterative Pre-order Traversal with Stack (O(n) time, O(n) space)
This method simulates preorder traversal using an explicit stack. Push the root node first. For each popped node, push its right child and then its left child so the left subtree is processed next. Rewire pointers by setting the current node’s right pointer to the next node on the stack and clearing left. The stack preserves preorder ordering without recursion. Time complexity remains O(n) since each node is pushed and popped once. Space complexity becomes O(n) in the worst case for skewed trees.
Both methods restructure the Binary Tree in-place without creating new nodes. The recursive approach is compact and mirrors the definition of preorder traversal. The iterative stack approach avoids recursion depth limits and provides more explicit control over traversal order.
Recommended for interviews: The recursive preorder DFS is usually the expected explanation because it clearly demonstrates pointer manipulation during traversal. Interviewers want to see that you understand preorder processing and in-place tree modification. The iterative stack version is a strong alternative when discussing recursion limits or implementing traversal without the call stack.
This approach involves a recursive pre-order traversal of the tree. The idea is to recursively flatten the left and right subtrees, then append the flattened left subtree between the root and the flattened right subtree.
The steps are as follows:
This leverage the pre-order traversal principle: Root → Left → Right.
This code defines a flatten function for recursively transforming a binary tree into a linked list in pre-order format. It first flattens the left and right subtrees, then rearranges the pointers of the root node.
Time Complexity: O(n) where n is the number of nodes in the tree since each node is visited once.
Space Complexity: O(n) due to the recursive call stack on an unbalanced tree.
This approach simplifies the recursive method by using a stack to maintain state information. By using controlled use of stack structures, we can modify the tree iteratively.
The algorithm progresses with these steps:
This achieves similar logic as recursion but without directly using the call stack by using our custom stack for maintaining traversal state.
This C code leverages a custom stack to iteratively implement pre-order traversal. Nodes are processed such that when a node is visited, it pushes its right and left children onto the stack. The list is reordered inline using right field connections.
Time Complexity: O(n) because every node is processed once.
Space Complexity: O(n), matching the worst-case stack usage when all nodes are in a single path.
The visit order of preorder traversal is "root, left subtree, right subtree". After the last node of the left subtree is visited, the right subtree node of the root node will be visited next.
Therefore, for the current node, if its left child node is not null, we find the rightmost node of the left subtree as the predecessor node, and then assign the right child node of the current node to the right child node of the predecessor node. Then assign the left child node of the current node to the right child node of the current node, and set the left child node of the current node to null. Then take the right child node of the current node as the next node and continue processing until all nodes are processed.
The time complexity is O(n), where n is the number of nodes in the tree. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Go
| Approach | Complexity |
|---|---|
| Recursive Pre-order Traversal | Time Complexity: |
| Iterative Pre-order Traversal | Time Complexity: |
| Find Predecessor Node | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Pre-order Traversal | O(n) | O(h) | Preferred in interviews; concise DFS logic and natural preorder traversal |
| Iterative Pre-order Traversal (Stack) | O(n) | O(n) | When avoiding recursion or handling deep trees where recursion depth could overflow |
L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Java • take U forward • 305,660 views views
Watch 9 more video solutions →Practice Flatten Binary Tree to Linked List with our built-in code editor and test cases.
Practice on FleetCode