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.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x
This Java solution similarly utilizes recursion to adjust the tree into a flattened linked list. It handles the left and right subtrees separately and then links them using iteration to adjust the right pointers.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct StackNode {
11 struct TreeNode* node;
12 struct StackNode* next;
13};
14
15void push(struct StackNode** stack, struct TreeNode* node) {
16 struct StackNode* new_node = (struct StackNode*)malloc(sizeof(struct StackNode));
17 new_node->node = node;
18 new_node->next = *stack;
19 *stack = new_node;
20}
21
22struct TreeNode* pop(struct StackNode** stack) {
23 if (!*stack) return NULL;
24 struct StackNode* tmp = *stack;
25 struct TreeNode* node = tmp->node;
26 *stack = tmp->next;
27 free(tmp);
28 return node;
29}
30
31void flatten(struct TreeNode* root) {
32 if (!root) return;
33 struct StackNode* stack = NULL;
34 push(&stack, root);
35
36 while (stack) {
37 struct TreeNode* curr = pop(&stack);
38
39 if (curr->right) {
40 push(&stack, curr->right);
41 }
42 if (curr->left) {
43 push(&stack, curr->left);
44 }
45
46 if (stack) {
47 curr->right = stack->node;
48 }
49 curr->left = NULL;
50 }
51}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.