142. Flatten Binary Tree to Linked List
🔗 LeetCode Problem: 114. Flatten Binary Tree to Linked List
📊 Difficulty: Medium
🏷️ Topics: Binary Trees, DFS, Preorder, In-place, Linked List, Post-order
Problem Statement
Given the root of a binary tree, flatten the tree into a "linked list":
- The "linked list" should use the same
TreeNodeclass where therightchild pointer points to the next node in the list and theleftchild pointer is alwaysnull. - The "linked list" should be in the same order as a preorder traversal of the binary tree.
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]
Follow up: Can you flatten the tree in-place (with O(1) extra space)?
Constraints:
- The number of nodes in the tree is in the range [0, 2000]
- -100 <= Node.val <= 100
🌳 Visual Understanding - The Complete Transformation!
What Does "Flatten" Mean?
ORIGINAL TREE:
1
/ \
2 5
/ \ \
3 4 6
FLATTENED "LINKED LIST":
1
\
2
\
3
\
4
\
5
\
6
Key observations:
✓ All nodes connected via RIGHT pointers
✓ All LEFT pointers become null
✓ Order follows PREORDER traversal (1,2,3,4,5,6)
✓ Same TreeNode objects, just relinked!
✓ In-place transformation (no new nodes created)
Why Preorder?
Preorder = Root → Left subtree → Right subtree
Example tree: 1
/ \
2 5
/ \ \
3 4 6
Preorder visits:
1 (root) → 2,3,4 (entire left) → 5,6 (entire right)
= [1, 2, 3, 4, 5, 6]
This is EXACTLY the flattened order we need! ✓
Step-by-Step Visual Transformation:
STEP 0: Original
1
/ \
2 5
/ \ \
3 4 6
STEP 1: Flatten left subtree (2)
1 2 (flattened)
/ \ \
? 5 3
\
4
STEP 2: Flatten right subtree (5)
1 5 (flattened)
/ \ \
? ? 6
STEP 3: Connect at root (1)
- Move flattened left (2→3→4) to right of 1
- Attach flattened right (5→6) to end
1
\
2
\
3
\
4
\
5
\
6
DONE! Perfect chain! ✨
🧠 The AHA Moment - Post-order Recursion!
The Key Insight:
To flatten a tree:
1. Flatten LEFT subtree (recursively)
2. Flatten RIGHT subtree (recursively)
3. Connect them at root:
root → flattened_left → flattened_right
Why POST-ORDER?
We need children FLATTENED before we connect them!
If we try to connect before flattening:
Children aren't in the right form yet! ✗
Post-order processes children FIRST:
Children are already flattened! ✓
Visual Example:
Tree:
1
/ \
2 3
Post-order recursion:
1. flatten(2) → Already a leaf, done!
Result: 2 (no changes)
2. flatten(3) → Already a leaf, done!
Result: 3 (no changes)
3. flatten(1) → Now connect:
- Save right: temp = 3
- Move left to right: 1.right = 2
- Clear left: 1.left = null
- Find end of 2: it's 2 itself
- Attach temp: 2.right = 3
Result: 1→2→3 ✓
Children flattened BEFORE parent connects them!
🧠 Recursive Thinking - Building the Solution
Base Case:
What's the simplest tree to flatten?
Case 1: null → Nothing to do, return
Case 2: Leaf node → Already flat! No children to connect
if (root == null) return;
For leaves, the recursion handles them naturally:
flatten(null) → returns immediately
No left or right → nothing to connect
Already in "flattened" form!
Recursive Case:
For any node with children:
STEP 1: Flatten children (POST-ORDER!)
flatten(root.left) // Left subtree now flattened
flatten(root.right) // Right subtree now flattened
STEP 2: Save right subtree (will be overwritten!)
TreeNode tempRight = root.right
STEP 3: Move flattened left to right
root.right = root.left
root.left = null
STEP 4: Find end of moved left subtree
TreeNode current = root
while (current.right != null):
current = current.right
STEP 5: Attach saved right subtree
current.right = tempRight
Result: root → left chain → right chain ✓
🎯 Solution 1: Recursive Post-order (Clearest!)
Implementation:
class Solution {
public void flatten(TreeNode root) {
// Base case: null tree
if (root == null) {
return;
}
// POST-ORDER: Flatten children FIRST
// WHY? Need subtrees flattened before connecting
flatten(root.left);
flatten(root.right);
// Now both children are flattened chains
// Time to connect at current node
// STEP 1: Save right subtree
// WHY? About to overwrite root.right with left!
TreeNode tempRight = root.right;
// STEP 2: Move left chain to right
// WHY? Preorder visits left before right
root.right = root.left;
root.left = null; // Clear left pointer
// STEP 3: Find end of moved left chain
// WHY? Need to attach tempRight at the END
TreeNode current = root;
while (current.right != null) {
current = current.right;
}
// STEP 4: Attach saved right chain
current.right = tempRight;
// Done! root → left chain → right chain ✓
}
}
Why Each Step Matters:
If we skip saving tempRight:
root.right = root.left // Lost reference to right!
// Can never attach right subtree ✗
If we don't find the end:
current.right = tempRight // Attaches at wrong place!
// Loses part of left subtree ✗
If we don't clear left:
root.left still has value
// Not a true "linked list" ✗
Every step is CRITICAL! 🎯
🔍 Detailed Dry Run - Complete Recursion Visualization
Tree:
1
/ \
2 5
/ \ \
3 4 6
Complete Call Stack with Tree States:
═══════════════════════════════════════════════════
CALL STACK VISUALIZATION
═══════════════════════════════════════════════════
Level 0: flatten(1)
│
├─ Tree state at start:
│ 1
│ / \
│ 2 5
│ / \ \
│ 3 4 6
│
├─ LEFT: flatten(2) ───────────────────────────────┐
│ │
│ Level 1: flatten(2) │
│ │ │
│ ├─ Tree state: │
│ │ 2 │
│ │ / \ │
│ │ 3 4 │
│ │ │
│ ├─ LEFT: flatten(3) ───────────────────────┐ │
│ │ │ │
│ │ Level 2: flatten(3) │ │
│ │ │ │ │
│ │ ├─ Tree state: 3 (leaf) │ │
│ │ ├─ LEFT: flatten(null) → return │ │
│ │ ├─ RIGHT: flatten(null) → return │ │
│ │ ├─ No children, nothing to connect │ │
│ │ └─ return │ │
│ │ │ │
│ ├─ RIGHT: flatten(4) ──────────────────────┐ │
│ │ │ │
│ │ Level 2: flatten(4) │ │
│ │ │ │ │
│ │ ├─ Tree state: 4 (leaf) │ │
│ │ ├─ LEFT: flatten(null) → return │ │
│ │ ├─ RIGHT: flatten(null) → return │ │
│ │ ├─ No children, nothing to connect │ │
│ │ └─ return │ │
│ │ │ │
│ ├─ Now connect at node 2: │ │
│ │ │ │
│ │ BEFORE connection: │ │
│ │ 2 │ │
│ │ / \ │ │
│ │ 3 4 │ │
│ │ │ │
│ │ STEP 1: tempRight = 4 │ │
│ │ STEP 2: 2.right = 3, 2.left = null │ │
│ │ STEP 3: Find end (current = 2 → 3) │ │
│ │ STEP 4: 3.right = 4 │ │
│ │ │ │
│ │ AFTER connection: │ │
│ │ 2 │ │
│ │ \ │ │
│ │ 3 │ │
│ │ \ │ │
│ │ 4 │ │
│ │ │ │
│ └─ return │ │
│ │
├─ RIGHT: flatten(5) ──────────────────────────────┐
│ │
│ Level 1: flatten(5) │
│ │ │
│ ├─ Tree state: │
│ │ 5 │
│ │ \ │
│ │ 6 │
│ │ │
│ ├─ LEFT: flatten(null) → return │
│ │ │
│ ├─ RIGHT: flatten(6) ───────────────────────┐ │
│ │ │ │
│ │ Level 2: flatten(6) │ │
│ │ │ │ │
│ │ ├─ Tree state: 6 (leaf) │ │
│ │ ├─ LEFT: flatten(null) → return │ │
│ │ ├─ RIGHT: flatten(null) → return │ │
│ │ └─ return │ │
│ │ │ │
│ ├─ Now connect at node 5: │ │
│ │ │ │
│ │ BEFORE: │ │
│ │ 5 │ │
│ │ \ │ │
│ │ 6 │ │
│ │ │ │
│ │ STEP 1: tempRight = 6 │ │
│ │ STEP 2: 5.right = null, 5.left = null │ │
│ │ STEP 3: Find end (current = 5, stop) │ │
│ │ STEP 4: 5.right = 6 │ │
│ │ │ │
│ │ AFTER: │ │
│ │ 5 │ │
│ │ \ │ │
│ │ 6 │ │
│ │ (No change, already flattened!) │ │
│ │ │ │
│ └─ return │ │
│ │
├─ Now connect at node 1: │
│ │
│ BEFORE connection: │
│ 1 │
│ / \ │
│ 2 5 (where 2→3→4 and 5→6) │
│ \ \ │
│ 3 6 │
│ \ │
│ 4 │
│ │
│ STEP 1: tempRight = 5 (points to 5→6) │
│ STEP 2: 1.right = 2 (points to 2→3→4) │
│ 1.left = null │
│ STEP 3: Find end of moved chain │
│ current = 1 → 2 → 3 → 4 (stop!) │
│ STEP 4: 4.right = 5 (attach 5→6) │
│ │
│ AFTER connection: │
│ 1 │
│ \ │
│ 2 │
│ \ │
│ 3 │
│ \ │
│ 4 │
│ \ │
│ 5 │
│ \ │
│ 6 │
│ │
└─ DONE! Perfect chain! ✨ │
═══════════════════════════════════════════════════
FINAL RESULT: 1→2→3→4→5→6 (all via right pointers)
═══════════════════════════════════════════════════
🎯 Solution 2: Iterative Morris-like (O(1) Space!) - DETAILED
The Challenge:
Can we flatten WITHOUT recursion?
→ No call stack = O(1) space!
Key insight:
At each node with left subtree, we need to:
1. Insert left subtree between current and right
2. Do this WITHOUT recursion!
How?
Process nodes left-to-right, top-to-bottom
At each node: handle its left subtree completely
Then move right (which now includes moved left)
The Morris-like Strategy Explained:
Core idea:
For node with left child:
BEFORE:
current
/ \
left right
WANT:
current
\
left
\
(end of left subtree)
\
right
How?
1. Find END of left subtree (rightmost node)
2. Connect end to right subtree
3. Move left to right position
4. Clear left pointer
5. Continue right (now processes moved left)
Visual Example - Step by Step:
INITIAL TREE:
1
/ \
2 5
/ \ \
3 4 6
Goal: 1→2→3→4→5→6
═══════════════════════════════════════════════════
STEP-BY-STEP TRANSFORMATION
═══════════════════════════════════════════════════
STEP 1: Process node 1
───────────────────────────────────────
Current tree:
1
/ \
2 5
/ \ \
3 4 6
1.a) current = 1, left exists (2)
1.b) Find rightmost of left subtree:
Start at 2
2
/ \
3 4
2.right exists? YES (4)
Move to 4
4.right exists? NO
STOP at 4 ✓
rightmost = 4
1.c) Connect rightmost to current.right:
4.right = 5
Now 4 points to 5:
2
/ \
3 4 → 5
\
6
1.d) Move left to right:
1.right = 2
1.e) Clear left:
1.left = null
Result after step 1:
1
\
2
/ \
3 4 → 5
\
6
Note: Node 4 is connected to 5!
This preserves the original right subtree!
Move to next: current = 1.right = 2
───────────────────────────────────────
STEP 2: Process node 2
───────────────────────────────────────
Current tree:
1
\
2
/ \
3 4 → 5
\
6
2.a) current = 2, left exists (3)
2.b) Find rightmost of left subtree:
Start at 3
3.right exists? NO
STOP at 3 ✓
rightmost = 3
2.c) Connect rightmost to current.right:
3.right = 4 (which points to 5)
Now: 3 → 4 → 5 → 6
2.d) Move left to right:
2.right = 3
2.e) Clear left:
2.left = null
Result after step 2:
1
\
2
\
3
\
4 → 5
\
6
Move to next: current = 2.right = 3
───────────────────────────────────────
STEP 3: Process node 3
───────────────────────────────────────
Current tree:
1
\
2
\
3
\
4 → 5
\
6
3.a) current = 3, left exists? NO
3.b) No left child, nothing to process
Move to next: current = 3.right = 4
───────────────────────────────────────
STEP 4: Process node 4
───────────────────────────────────────
Current tree:
1
\
2
\
3
\
4
\
5
\
6
4.a) current = 4, left exists? NO
4.b) No left child, nothing to process
Move to next: current = 4.right = 5
───────────────────────────────────────
STEP 5: Process node 5
───────────────────────────────────────
5.a) current = 5, left exists? NO
5.b) No left child, nothing to process
Move to next: current = 5.right = 6
───────────────────────────────────────
STEP 6: Process node 6
───────────────────────────────────────
6.a) current = 6, left exists? NO
6.b) No left child, nothing to process
Move to next: current = 6.right = null
───────────────────────────────────────
DONE! current = null
───────────────────────────────────────
FINAL FLATTENED TREE:
1
\
2
\
3
\
4
\
5
\
6
SUCCESS! ✓
Implementation with Detailed Comments:
class Solution {
public void flatten(TreeNode root) {
TreeNode current = root;
// Process nodes from left to right
while (current != null) {
// Only process if left child exists
if (current.left != null) {
// STEP 1: Find rightmost node of left subtree
// This is the END of the left subtree chain
TreeNode rightmost = current.left;
while (rightmost.right != null) {
rightmost = rightmost.right;
}
// At this point, rightmost.right == null
// rightmost is the LAST node in left subtree
// STEP 2: Connect rightmost to current's right
// This PRESERVES the original right subtree
// It will be attached after the entire left subtree
rightmost.right = current.right;
// STEP 3: Move left subtree to right
// Now current.right points to the left subtree
current.right = current.left;
// STEP 4: Clear left pointer
// After moving, left should be null (linked list property)
current.left = null;
// After these steps:
// - Left subtree is now on the right
// - End of left subtree connects to original right
// - Left pointer is null
}
// STEP 5: Move to next node
// This will process the moved left subtree next
current = current.right;
}
}
}
Why This Algorithm Works:
KEY INSIGHT: Rightmost node connection!
When we find rightmost of left subtree,
we connect it to the current right subtree.
This ensures: left → ... → rightmost → right
Example:
current (1)
/ \
2 5
/ \ \
3 4 6
Rightmost of left = 4
Connect: 4 → 5
Then move left to right: 1 → 2
Result: 1 → 2 → 3 → 4 → 5 → 6
The rightmost connection is KEY! 🔑
Why O(1) Space?
Space used:
- current pointer: O(1)
- rightmost pointer: O(1)
- NO recursion stack: O(0)
- NO extra data structures: O(0)
Total: O(1) extra space! ✓
Time: O(n) - each node visited at most twice
1. As current
2. When finding rightmost
Still efficient! 🚀
Common Mistakes - Morris Approach:
❌ MISTAKE 1: Not finding true rightmost
rightmost = current.left;
// Forgot to traverse right!
This only gets immediate left child,
not the END of left subtree! ✗
✓ CORRECT:
while (rightmost.right != null) {
rightmost = rightmost.right;
}
❌ MISTAKE 2: Not connecting rightmost
rightmost = current.left;
current.right = current.left;
current.left = null;
// Lost the original right subtree! ✗
✓ CORRECT:
rightmost.right = current.right; // Save it first!
current.right = current.left;
❌ MISTAKE 3: Clearing left before moving
current.left = null;
current.right = current.left; // Now null! ✗
✓ CORRECT: Move first, clear second
current.right = current.left;
current.left = null;
Visual Comparison - Recursive vs Iterative:
RECURSIVE (Post-order):
✓ Cleaner, more intuitive
✓ Natural top-down flow
✗ O(h) space (call stack)
✗ Can't optimize space
ITERATIVE (Morris-like):
✓ O(1) space! No recursion!
✓ Same time complexity
✗ More complex logic
✗ Harder to understand initially
Both correct! Choose based on constraints:
- Space critical? → Iterative
- Clarity critical? → Recursive
📊 Complexity Analysis
Recursive Solution:
Time Complexity: O(n²) worst case, O(n log n) average
Visit each node: O(n)
At each node:
- Flatten children: covered by "visit each"
- Find end of moved left: O(k) where k = left subtree size
Worst case (left-skewed tree):
1
/
2
/
3
/
4
At 1: find end through all left nodes (O(n))
At 2: find end (O(n-1))
At 3: find end (O(n-2))
...
Total: O(n) + O(n-1) + ... + O(1) = O(n²)
Average case (balanced): O(n log n)
Each level: O(n/2^i) nodes × O(i) to find end
Sum over levels: O(n log n)
Space Complexity: O(h)
Recursion call stack: O(h) where h = height
Best case (balanced): O(log n)
Worst case (skewed): O(n)
Iterative Solution:
Time Complexity: O(n)
Each node visited at most twice:
1. Once as current
2. Once when finding rightmost
But wait - finding rightmost can traverse multiple nodes!
Actually: Each node visited exactly ONCE
- Either as current OR as part of rightmost search
- But never both (once processed, moved to right)
Total: O(n) ✓
This is BETTER than recursive! 💡
Space Complexity: O(1)
Only use a few pointers:
- current
- rightmost
No recursion stack!
True O(1) space! ✓
This satisfies the follow-up! 🎯
⚠️ Common Mistakes
Mistake 1: Not Saving Right Subtree
// ❌ WRONG - Lost right subtree!
flatten(root.left);
flatten(root.right);
root.right = root.left; // Overwrites root.right!
root.left = null;
// Now we have no reference to original right subtree!
// It's LOST! ✗
// ✓ CORRECT - Save first!
TreeNode tempRight = root.right; // Save it!
root.right = root.left;
root.left = null;
// Now we can attach tempRight later
current.right = tempRight; ✓
Mistake 2: Not Finding End of Moved Subtree
// ❌ WRONG - Attaches at wrong place!
root.right = root.left;
root.left = null;
root.right.right = tempRight; // WRONG! root.right might have children!
// Example tree: 1
// /
// 2
// /
// 3
//
// Would create: 1
// \
// 2 → tempRight (lost 3!) ✗
// /
// 3
// ✓ CORRECT - Find the actual END
TreeNode current = root;
while (current.right != null) {
current = current.right;
}
current.right = tempRight; // Attach at END ✓
Mistake 3: Forgetting to Set Left to Null
// ❌ WRONG - Left pointers remain!
root.right = root.left;
// Forgot: root.left = null;
flatten(root.right);
// Result: 1
// / \ ← Both pointers exist!
// 2 2 (same node!)
//
// Not a "linked list"! ✗
// ✓ CORRECT - Always clear left!
root.right = root.left;
root.left = null; // Critical! ✓
Mistake 4: Wrong Recursion Order (Preorder)
// ❌ WRONG - Preorder recursion
// (Modifies tree BEFORE processing children)
TreeNode tempRight = root.right;
root.right = root.left;
root.left = null;
flatten(root.left); // Now null! Lost reference! ✗
flatten(root.right);
// We modified tree before recursing!
// Lost access to original children! ✗
// ✓ CORRECT - Post-order
flatten(root.left); // Flatten children FIRST
flatten(root.right);
// NOW reconnect (children already processed)
TreeNode tempRight = root.right;
root.right = root.left;
root.left = null;
// ... ✓
Mistake 5: Iterative - Moving Right Before Clearing Left
// ❌ WRONG - Creates cycle!
while (current != null) {
if (current.left != null) {
rightmost.right = current.right;
current.right = current.left;
// Forgot: current.left = null;
current = current.right; // Now current and current.left both point to same node!
}
}
// Creates circular reference! ✗
// ✓ CORRECT - Clear left before moving
current.left = null; // Clear first!
current = current.right; ✓
🎯 Pattern Recognition - In-Place Tree Transformation
Core Pattern: Post-order Tree Restructuring
Template for in-place transformations:
void transform(TreeNode node) {
if (node == null) return;
// POST-ORDER: Transform children first
// WHY? Need them in final form before connecting
TreeNode savedLeft = node.left;
TreeNode savedRight = node.right;
transform(savedLeft);
transform(savedRight);
// Now reconnect with new structure
reconnect(node, savedLeft, savedRight);
}
Related Problems:
1. Invert Binary Tree (Problem 136)
In-place transformation
Swaps left and right
Simpler: just swap pointers!
2. Convert BST to Sorted Doubly Linked List
In-place restructuring
Uses inorder traversal (sorted)
Connect nodes with left/right as prev/next
Similar connection logic!
3. Binary Tree to Circular Doubly Linked List
In-place + circular connection
Track first and last nodes
Connect tail to head at end
4. Serialize and Deserialize Binary Tree
Not in-place, but related
Uses preorder for serialization
Same order as flatten! ✓
When to Use This Pattern:
✓ "In-place" or "O(1) space" in problem
✓ Restructure tree keeping same nodes
✓ Change pointer relationships
✓ Transform to list/different structure
✓ Preserve certain traversal order
✓ No new nodes created
📝 Quick Revision Notes
🎯 Core Concept
Flatten tree to right-skewed "linked list" following preorder order. All nodes connected via right pointers, left = null. Two approaches: (1) Recursive post-order (flatten children, then connect - clearest logic), (2) Iterative Morris-like (O(1) space! - at each node, find rightmost of left, connect to right, move left to right). Key insight: Process children FIRST (post-order), then reconnect at parent.
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public void flatten(TreeNode root) {
// // Approach 1 - straight forward - check visual understanding section.
// usingPostOrder(root);
// Approach 2 - Morris
usingMorris(root);
}
private void usingMorris(TreeNode root) {
// Steps - check example in LC to understand these steps
// 1. Find right most node of the left subtree (of root).
// 2. Attach the right subtree (of root) to the above right most end of the left subtree.
// 3. Now, move to next node which is right of root (root.right). No more left exists at root now.
// 4. Repeat steps 1,2,3 for every root (and later root = root.right) only when root.left exists
while (root != null) {
// Above steps 1,2,3 in case only left exists. Else, proceed to right
if(root.left != null) {
// Step 1 - finding the right most node of the left subtree.
TreeNode curr = root.left;
while (curr.right != null) {
curr = curr.right;
}
// Step 2
// attach the current right subtree to above curr.
// move current left subtree to root right
// nullify root left as its moved to right.
curr.right = root.right;
root.right = root.left;
root.left = null;
// Step 3 - move to next node. Still my root is at 1.
root = root.right;
} else {
root = root.right;
}
}
}
private void usingPostOrder(TreeNode root) {
// base case - return in case of leaf node
if(root == null) {
return;
}
// Steps
// 1. flatten left
// 2. flatten right
// 3. connect left to root and right to left (handle disconnects while connecting)
usingPostOrder(root.left); // step 1
usingPostOrder(root.right); // step 2
TreeNode temp = root.right; // preserve right to connect to end of left subtree
// connecting left subtree to root right and nullify root left.
root.right = root.left;
root.left = null;
// since left subtree is flattened, traverse towards the end of flattened subtree, which
// is now a linked list. At the end of it, attach previously saved right.
TreeNode curr = root;
while (curr != null && curr.right != null) {
curr = curr.right; // no need to bother about left as all child subtrees would be flattened by now and no left children
}
curr.right = temp; // attached right flattened sub tree to end of the left flattened sub tree
}
public static void main(String[] args) {
Solution s = new Solution();
TreeNode root1 = TreeNode.buildTree(new Integer[] {1,2,5,3,4,null,6});
s.flatten(root1);
TreeNode.print(root1);
}
}
🔑 Key Insights
Why Post-Order?
Need children FLATTENED before connecting!
Preorder would modify tree during recursion:
✗ Lose references to children
✗ Can't recurse properly
Post-order processes children FIRST:
✓ Children already in final form
✓ Safe to reconnect at parent
Children first, parent last = POST-ORDER! 🎯
The Reconnection Dance:
At each node (after children flattened):
1. Save right → tempRight
WHY? Will be overwritten
2. Move left to right
WHY? Preorder visits left first
3. Set left = null
WHY? "Linked list" has no lefts
4. Find end of moved left
WHY? Need to attach tempRight there
5. Attach tempRight
WHY? Complete the chain!
All 5 steps required! 🔗
O(1) Space Achievement:
Recursive: O(h) space (call stack)
Iterative: O(1) space! ✓
How?
- No recursion (no call stack)
- Only few pointers (current, rightmost)
- Process left-to-right, top-to-bottom
This satisfies the follow-up! 🎯
🎪 Memory Aid
"Post-order: children first, then connect!"
"Save before overwrite!"
"Find end, then attach!"
"Iterative = O(1) space magic!" ✨
⚠️ Don't Forget
- Post-order recursion (children before parent!)
- Save right subtree (before overwriting!)
- Set left = null (all lefts must be null!)
- Find END (not just root.right!)
- Iterative for O(1) (no recursion stack!)
- Preorder defines order (1→2→3→4→5→6!)
🎉 Congratulations!
You've mastered in-place tree transformation!
What You Learned:
✅ In-place restructuring - Modify without new nodes
✅ Post-order processing - Children before parent
✅ Pointer manipulation - Save, move, find, connect
✅ Preorder application - Order matches flatten
✅ O(1) space solution - Iterative Morris-like approach
✅ Complex tree transformation - Multi-step reconnection
The Complete Picture:
Problem 136: Invert
- Simple swap
- Can use any order
Problem 142: Flatten
- Complex restructuring
- MUST use post-order
- Preorder result order
- O(1) space possible
Advanced transformation mastery! 🏆
Interview Mastery:
Interviewer: "Flatten tree in-place"
Your approach:
1. "Preorder traversal order" ✓
2. "Post-order recursion to process" ✓
3. "Save-move-find-attach pattern" ✓
4. "Can optimize to O(1) space" ✓
Codes recursive in 8 minutes ✓
Explains iterative optimization ✓
Handles all edge cases ✓
Perfect response! 💯
You're a tree transformation expert! 🌳🔧✨