Language Selection
Choose your preferred programming language
Showing: Python
Flatten Binary Tree to Linked List
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 preorder traversal of the binary tree.
Examples
Example 1:
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Explanation:
Before: After:
1 1
/ \ \
2 5 2
/ \ \ \
3 4 6 3
\
4
\
5
\
6
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [0]
Output: [0]
Constraints
0 <= Number of nodes <= 2000-100 <= Node.val <= 100
Approach 1: Recursive with Right Subtree Handling (Optimal)
Algorithm
Use postorder traversal to flatten the tree. For each node, flatten left and right subtrees, then attach the flattened left subtree to the right of current node.
Steps:
- Recursively flatten left and right subtrees
- Store the right subtree temporarily
- Move flattened left subtree to right of current node
- Attach the stored right subtree to the end of the flattened left subtree
Implementation
Python:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def flatten(root):
"""
Flatten binary tree to linked list using recursion
Time: O(n)
Space: O(h) where h is height of tree
"""
def dfs(node):
if not node:
return None
# Flatten left and right subtrees
left_tail = dfs(node.left)
right_tail = dfs(node.right)
# If left subtree exists, move it to right
if node.left:
# Store right subtree
right_subtree = node.right
# Move left subtree to right
node.right = node.left
node.left = None
# Attach original right subtree to end of left subtree
left_tail.right = right_subtree
# Return the tail of current subtree
return right_tail or left_tail or node
dfs(root)
Java:
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;
}
}
class Solution {
public void flatten(TreeNode root) {
dfs(root);
}
private TreeNode dfs(TreeNode node) {
if (node == null) {
return null;
}
// Flatten left and right subtrees
TreeNode leftTail = dfs(node.left);
TreeNode rightTail = dfs(node.right);
// If left subtree exists, move it to right
if (node.left != null) {
// Store right subtree
TreeNode rightSubtree = node.right;
// Move left subtree to right
node.right = node.left;
node.left = null;
// Attach original right subtree to end of left subtree
leftTail.right = rightSubtree;
}
// Return the tail of current subtree
return rightTail != null ? rightTail : (leftTail != null ? leftTail : node);
}
}
Go:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func flatten(root *TreeNode) {
dfs(root)
}
func dfs(node *TreeNode) *TreeNode {
if node == nil {
return nil
}
// Flatten left and right subtrees
leftTail := dfs(node.Left)
rightTail := dfs(node.Right)
// If left subtree exists, move it to right
if node.Left != nil {
// Store right subtree
rightSubtree := node.Right
// Move left subtree to right
node.Right = node.Left
node.Left = nil
// Attach original right subtree to end of left subtree
leftTail.Right = rightSubtree
}
// Return the tail of current subtree
if rightTail != nil {
return rightTail
}
if leftTail != nil {
return leftTail
}
return node
}
JavaScript:
class TreeNode {
constructor(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}
}
function flatten(root) {
function dfs(node) {
if (!node) {
return null;
}
// Flatten left and right subtrees
const leftTail = dfs(node.left);
const rightTail = dfs(node.right);
// If left subtree exists, move it to right
if (node.left) {
// Store right subtree
const rightSubtree = node.right;
// Move left subtree to right
node.right = node.left;
node.left = null;
// Attach original right subtree to end of left subtree
leftTail.right = rightSubtree;
}
// Return the tail of current subtree
return rightTail || leftTail || node;
}
dfs(root);
}
C#:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public void Flatten(TreeNode root) {
Dfs(root);
}
private TreeNode Dfs(TreeNode node) {
if (node == null) {
return null;
}
// Flatten left and right subtrees
TreeNode leftTail = Dfs(node.left);
TreeNode rightTail = Dfs(node.right);
// If left subtree exists, move it to right
if (node.left != null) {
// Store right subtree
TreeNode rightSubtree = node.right;
// Move left subtree to right
node.right = node.left;
node.left = null;
// Attach original right subtree to end of left subtree
leftTail.right = rightSubtree;
}
// Return the tail of current subtree
return rightTail ?? leftTail ?? node;
}
}
Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(h) - Recursion stack depth
Approach 2: Morris Traversal Style
Algorithm
Use a modified Morris traversal approach to flatten the tree in O(1) space.
Steps:
- For each node, find the rightmost node in its left subtree
- Attach the right subtree to this rightmost node
- Move the left subtree to the right
- Continue with the next node
Implementation
Python:
def flattenMorris(root):
"""
Morris traversal style flattening
Time: O(n)
Space: O(1)
"""
current = root
while current:
if current.left:
# Find rightmost node in left subtree
rightmost = current.left
while rightmost.right:
rightmost = rightmost.right
# Attach right subtree to rightmost node
rightmost.right = current.right
# Move left subtree to right
current.right = current.left
current.left = None
# Move to next node
current = current.right
Java:
public void flattenMorris(TreeNode root) {
TreeNode current = root;
while (current != null) {
if (current.left != null) {
// Find rightmost node in left subtree
TreeNode rightmost = current.left;
while (rightmost.right != null) {
rightmost = rightmost.right;
}
// Attach right subtree to rightmost node
rightmost.right = current.right;
// Move left subtree to right
current.right = current.left;
current.left = null;
}
// Move to next node
current = current.right;
}
}
Go:
func flattenMorris(root *TreeNode) {
current := root
for current != nil {
if current.Left != nil {
// Find rightmost node in left subtree
rightmost := current.Left
for rightmost.Right != nil {
rightmost = rightmost.Right
}
// Attach right subtree to rightmost node
rightmost.Right = current.Right
// Move left subtree to right
current.Right = current.Left
current.Left = nil
}
// Move to next node
current = current.Right
}
}
JavaScript:
function flattenMorris(root) {
let current = root;
while (current) {
if (current.left) {
// Find rightmost node in left subtree
let rightmost = current.left;
while (rightmost.right) {
rightmost = rightmost.right;
}
// Attach right subtree to rightmost node
rightmost.right = current.right;
// Move left subtree to right
current.right = current.left;
current.left = null;
}
// Move to next node
current = current.right;
}
}
C#:
public void FlattenMorris(TreeNode root) {
TreeNode current = root;
while (current != null) {
if (current.left != null) {
// Find rightmost node in left subtree
TreeNode rightmost = current.left;
while (rightmost.right != null) {
rightmost = rightmost.right;
}
// Attach right subtree to rightmost node
rightmost.right = current.right;
// Move left subtree to right
current.right = current.left;
current.left = null;
}
// Move to next node
current = current.right;
}
}
Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(1) - No extra space used
Key Insights
- Preorder Traversal: The flattened list follows preorder traversal order
- In-Place Modification: Modify the tree structure without creating new nodes
- Right Subtree Handling: Carefully handle the right subtree when moving left subtree
- Tail Tracking: Keep track of the tail of flattened subtrees
- Space Optimization: Morris traversal achieves O(1) space complexity
Edge Cases
- Empty Tree: Handle null root
- Single Node: Return the node as is
- Left Skewed: Only left children
- Right Skewed: Only right children
- Complete Tree: Both left and right children
Follow-up Questions
- Reverse Flatten: How would you unflatten the tree?
- Different Orders: Flatten using inorder or postorder?
- Circular List: Convert to circular linked list?
- Validation: Check if a tree is already flattened?
- Partial Flatten: Flatten only a subtree?
Common Mistakes
- Right Subtree Loss: Not properly handling the right subtree when moving left
- Tail Tracking: Not correctly tracking the tail of flattened subtrees
- Null Handling: Not handling null nodes properly
- Space Usage: Using extra space when in-place modification is required
- Order Confusion: Not maintaining preorder traversal order
Interview Tips
- Clarify Requirements: Ask about in-place modification and traversal order
- Discuss Approaches: Mention recursive, iterative, and Morris traversal approaches
- Handle Edge Cases: Discuss empty tree and single node scenarios
- Explain Algorithm: Walk through the subtree movement and tail tracking
- Consider Optimizations: Discuss space-time tradeoffs