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 <= 100O(1) extra space)?The goal of Flatten Binary Tree to Linked List is to transform a binary tree into a linked list in-place following the preorder traversal order. The final structure should use the right pointers to represent the linked list while all left pointers become null.
A common strategy is to simulate preorder traversal using Depth-First Search (DFS). One approach is a recursive DFS where you process the right subtree and left subtree in reverse preorder while keeping track of the previously visited node. Each node's right pointer is updated to point to the previously processed node, effectively building the flattened structure from the end.
Another popular solution uses a stack to iteratively perform preorder traversal. Nodes are processed while pushing right and left children to maintain correct ordering.
Both strategies ensure each node is visited once, giving O(n) time complexity. Space complexity depends on recursion depth or stack usage, which can be up to O(h) where h is the tree height.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive DFS (Reverse Preorder) | O(n) | O(h) |
| Iterative Stack-Based DFS | O(n) | O(h) |
| Morris Traversal / In-place Rewiring | O(n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
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.
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.
1#include <stdio.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
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.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar tree transformation questions frequently appear in FAANG-style interviews. It tests understanding of tree traversal, pointer manipulation, and in-place algorithm design.
The optimal approach uses Depth-First Search with preorder traversal while rearranging pointers in-place. A reverse preorder recursive method or Morris-style pointer rewiring can flatten the tree efficiently in O(n) time.
Yes, it can be solved using a Morris traversal style technique that rewires pointers during traversal. This approach achieves O(1) extra space while still maintaining O(n) time complexity.
A stack is commonly used to simulate preorder traversal iteratively. It helps maintain the correct processing order of nodes while updating pointers to create the linked list structure.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def flatten(self, root: TreeNode) -> None:
9 if not root:
10 return
11
12 stack = [root]
13
14 while stack:
15 current = stack.pop()
16
17 if current.right:
18 stack.append(current.right)
19
20 if current.left:
21 stack.append(current.left)
22
23 if stack:
24 current.right = stack[-1]
25
26 current.left = NoneThe Python iteration utilizes a stack to simulate recursion for flattening the tree by pre-order alignment. It extracts nodes from the stack in `right-first` fashion during each traversal iteration.