Log inSign up
mediumleetcodeNot Started

Flatten Binary Tree to Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, flatten the tree into a "linked list" in-place: - The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. - The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1 · Example 1: Standard Tree:

Input: root = [1, 2, 5, 3, 4, null, 6] Tree: 1 / \ 2 5 / \ \ 3 4 6
Output: [1, null, 2, null, 3, null, 4, null, 5, null, 6]
Explanation: Preorder traversal is 1 -> 2 -> 3 -> 4 -> 5 -> 6. Tree is transformed into a right-skewed chain.

Example 2 · Example 2: Empty Tree:

Input: root = []
Output: []
Explanation: Empty tree flattens to empty list.

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why in-place pointer rewiring requires careful order handling.
  • Master the Reverse Preorder trick (Right -> Left -> Root) with a prev pointer.
  • Implement the Morris Traversal flattening in strict O(1) auxiliary space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Flatten binary tree in-place.
  • Transform tree into right-skewed linked list in preorder sequence.
  • O(1) auxiliary space requirement.

Algorithmic Decision Tree:

  • If curr.left exists: predecessor = curr.left; while predecessor.right: predecessor = predecessor.right.
  • predecessor.right = curr.right.
  • curr.right = curr.left; curr.left = null.
  • curr = curr.right.

Connected Patterns:

Binary Tree Preorder TraversalInvert Binary TreePopulating Next Right Pointers in Each Node

1. Preorder Array Collection + Relinking

Intuition

Traverse tree in standard preorder and push pointers to an array. Then loop from 0 to n-2 setting nodes[i].right = nodes[i+1] and nodes[i].left = null.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Traverse tree preorder, storing TreeNode* in list.
  2. Step 2: Iterate through list from 0 to list.size() - 2.
  3. Step 3: list[i].right = list[i + 1]; list[i].left = null.
  4. Step 4: list.back().left = list.back().right = null.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void preorder(TreeNode* node, vector<TreeNode*>& nodes) {
10 if (!node) return;
11 nodes.push_back(node);
12 preorder(node->left, nodes);
13 preorder(node->right, nodes);
14 }
15 void flatten(TreeNode* root) {
16 if (!root) return;
17 vector<TreeNode*> nodes;
18 preorder(root, nodes);
19 for (int i = 0; i < (int)nodes.size() - 1; ++i) {
20 nodes[i]->left = nullptr;
21 nodes[i]->right = nodes[i + 1];
22 }
23 nodes.back()->left = nullptr;
24 nodes.back()->right = nullptr;
25 }
26};
27
28int main() {
29 // Sample driver execution
30 cout << "Execution completed successfully." << endl;
31 return 0;
32}
33

Time & Space Complexity

  • Time complexity: O(n) — Preorder traversal takes O(n); relinking takes O(n).
  • Space complexity: O(n) — Array stores n node references.

2. Reverse Preorder DFS (Right -> Left -> Root)

Intuition

By visiting Right -> Left -> Root, nodes are processed in exact reverse linked-list order. We maintain prev pointer (initially null). At each node: node.right = prev, node.left = null, prev = node.

When to apply: Clean recursive solution without extra array storage.

Algorithm

  1. Step 1: Maintain TreeNode* prev = null.
  2. Step 2: Helper flatten(node): if null return.
  3. Step 3: flatten(node.right); flatten(node.left).
  4. Step 4: node.right = prev; node.left = null; prev = node.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 TreeNode* prev = nullptr;
9public:
10 void flatten(TreeNode* root) {
11 if (!root) return;
12 flatten(root->right);
13 flatten(root->left);
14 root->right = prev;
15 root->left = nullptr;
16 prev = root;
17 }
18};
19
20int main() {
21 // Sample driver execution
22 cout << "Execution completed successfully." << endl;
23 return 0;
24}
25

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(h) — Recursion call stack takes O(h) space.

3. Morris Traversal In-Place Flattening (O(1) Auxiliary Space)

Intuition

Iterate while curr != null. If curr has a left child: find predecessor (rightmost node in curr's left subtree). Wire predecessor.right = curr.right. Move curr's left child to curr.right, and set curr.left = null. Advance curr = curr.right.

When to apply: Optimal gold-standard solution for strict O(1) space.

Algorithm

  1. Step 1: Set curr = root.
  2. Step 2: While curr != null:
  3. Step 3: If curr.left != null: pred = curr.left; while pred.right: pred = pred.right; pred.right = curr.right; curr.right = curr.left; curr.left = null.
  4. Step 4: curr = curr.right.

Morris Flatten Trace for root = [1, 2, 5]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Node 1 has left child 2
Visual state
Values and pointers at this exact step
tree
Root
1
L (Moving)
2
R (Attached)
5

Node order shown; add connections to display explicit tree edges.

curr: 1
Check / comparison
Predecessor 2.right set to 5
Decision / next transition
Link 2.right = 5. Move left branch to right branch.
Why this step matters

Step 1: Node 1 has left child 2. Find predecessor (rightmost of left subtree) = 2. Attach node 5 to 2's right.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void flatten(TreeNode* root) {
10 TreeNode* cur = root;
11 while (cur) {
12 if (cur->left) {
13 TreeNode* pred = cur->left;
14 while (pred->right) pred = pred->right;
15 pred->right = cur->right;
16 cur->right = cur->left;
17 cur->left = nullptr;
18 }
19 cur = cur->right;
20 }
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(n) — Each edge is traversed at most twice.
  • Space complexity: O(1) — Strictly O(1) auxiliary memory; no recursion, no queues, no lists.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Preorder Array RelinkingO(n)O(n)Collect nodes into array and rewire pointers in loop.Node array allocation.
2.Reverse Preorder DFSO(n)O(h)Right -> Left -> Root traversal rewires right = prev on unwind.Recursion depth.
3.Morris Traversal In-PlaceOptimalO(n)O(1)Connect predecessor.right to curr.right; move left to right.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root is null -> nothing to do.
  • Single node: left is null, right is null -> remains unchanged.
  • Already flattened (right-skewed): while loop never enters left branch, finishes in O(n).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by explaining the reverse preorder recursion (Right -> Left -> Root) because it is very intuitive.
  2. Then offer the Morris Traversal for O(1) space to demonstrate advanced algorithmic mastery.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.In the Morris in-place approach, why is curr.right attached to the rightmost node of curr.left (the predecessor)?

Back to DSA Sheet