How do you solve Flatten Binary Tree to Linked List on LeetCode?

Flatten Binary Tree to Linked List (LeetCode #114) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Each node's right child points to the next node in pre-order traversal.

What is the brute force solution for Flatten Binary Tree to Linked List?

The brute force approach for Flatten Binary Tree to Linked List is Brute Force, with O(n²) time complexity and O(n) space complexity. We can traverse the tree and collect nodes in a list, then rearrange them to create the linked list structure. This approach is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Flatten Binary Tree to Linked List?

Flatten Binary Tree to Linked List uses the following concepts: Linked List, Stack, Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Tree Traversal, In-place Modification.

What are the interview tips for Flatten Binary Tree to Linked List?

Always clarify whether in-place modification is required. Think about edge cases like empty trees or single-node trees. Explain your thought process clearly while coding.

What are common mistakes when solving Flatten Binary Tree to Linked List?

Not handling null cases properly, leading to NullPointerExceptions. Forgetting to set left pointers to null after rearranging.

#114

Flatten Binary Tree to Linked List

Medium

Linked ListStackTreeDepth-First SearchBinary TreeTree TraversalIn-place Modification

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

We can flatten the tree in-place using a recursive approach without needing extra space for a list. This is more efficient and meets the follow-up requirement.

⚙️

Algorithm

3 steps

1Step 1: Recursively flatten the left subtree and the right subtree.
2Step 2: Connect the flattened left subtree to the right of the current node.
3Step 3: Set the right pointer of the current node to the head of the flattened right subtree.

solution.py20 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def flatten(self, root: TreeNode) -> None:
10        if not root:
11            return
12        if root.left:
13            self.flatten(root.left)
14            temp = root.right
15            root.right = root.left
16            root.left = None
17            while root.right:
18                root = root.right
19            root.right = temp
20        self.flatten(root.right)

ℹ

Complexity note: The time complexity is O(n) because we visit each node once. The space complexity is O(1) since we are modifying the tree in place without using extra space.

1Each node's right child points to the next node in pre-order traversal.
2In-place modification is possible by rearranging pointers.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.