LeetCode 114: Flatten Binary Tree to Linked List Solution in Python – A Step-by-Step Guide

What Is LeetCode 114: Flatten Binary Tree to Linked List?

In LeetCode 114: Flatten Binary Tree to Linked List, you’re given the root of a binary tree, and your job is to transform it into a “linked list” in-place. The catch? The list must follow the preorder traversal order (root, left, right), and each node’s left child should be None, with its right child pointing to the next node in the sequence. For example, a tree like [1, 2, 5, 3, 4, None, 6] becomes a right-skewed list where 1 points to 2, 2 to 3, 3 to 4, 4 to 5, and 5 to 6—all with no left children.

Problem Statement

• Input: Root node of a binary tree (TreeNode).
• Output: None (modify the tree in-place).
• Rules:
• Flatten to a linked list using preorder traversal.
• Set each node’s left to None, right to the next node.
• Do it in-place (minimize extra space).

Constraints

• Number of nodes: 0 <= n <= 2000
• -100 <= Node.val <= 100

Examples

• Input: root = [1, 2, 5, 3, 4, None, 6]
• Output: [1, None, 2, None, 3, None, 4, None, 5, None, 6]
• Why: Preorder: 1, 2, 3, 4, 5, 6 → linked list.
• Input: root = []
• Output: []
• Why: Empty tree, nothing to flatten.
• Input: root = [0]
• Output: [0]
• Why: Single node is already a list.

Understanding the Problem: From Tree to Chain

To solve LeetCode 114: Flatten Binary Tree to Linked List in Python, we need to rearrange a binary tree into a right-skewed linked list following preorder traversal, all while modifying the tree in-place. A naive approach might be to collect all nodes in a list (O(n) space) and relink them, but the “in-place” hint pushes us toward minimal extra space. We’ll explore:

• Best Solution (Morris-like Preorder): O(n) time, O(1) space—rewires the tree on the fly.
• Alternative Solution (Recursive Preorder): O(n) time, O(n) space—uses the call stack.

Let’s dive into the Best Solution—a Morris-like approach—and break it down step-by-step.

Best Solution: Morris-like Preorder Traversal

Why This Is the Best Solution

The Morris-like preorder traversal is the champ here because it flattens the tree in O(n) time with O(1) space—no recursion, no extra arrays, just clever pointer juggling. It reuses the tree’s own structure to build the list, making it memory-efficient and elegant. It’s like a magician reweaving the tree into a chain without needing extra props!

How It Works

Here’s the strategy:

• Step 1: Process Node-by-Node:
• Start at the root, work iteratively.
• Step 2: Handle Left Subtree:
• If a node has a left child:
• Find the rightmost node in the left subtree (the “predecessor”).
• Move the left subtree to the right of the current node.
• Set the current node’s left to None.
• Link the predecessor’s right to the original right child.
• Step 3: Move Forward:
• Advance to the new right child (former left subtree).
• Step 4: Repeat:
• Continue until all nodes are processed.

Step-by-Step Example

Example: root = [1, 2, 5, 3, 4, None, 6]

• Initial Tree:

1 / \ 2 5 / \ \ 3 4 6

• Step 1: root = 1:
• Left = 2, Right = 5.
• Find rightmost in left (2’s subtree) = 4.
• 1.right = 2, 4.right = 5, 1.left = None.
• Tree:

1 \ 2 / \ 3 4 \ 5 \ 6

• Step 2: root = 2:
• Left = 3, Right = 4.
• Rightmost in left = 3 (no right child).
• 2.right = 3, 3.right = 4, 2.left = None.
• Tree:

1 \ 2 \ 3 \ 4 \ 5 \ 6

• Step 3: root = 3:
• No left, move to 4.
• Step 4: root = 4:
• No left, move to 5.
• Step 5: root = 5:
• No left, move to 6.
• Step 6: root = 6:
• No left, done.
• Result: [1, None, 2, None, 3, None, 4, None, 5, None, 6].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        # Start at root
        curr = root

        # Iterate until no nodes left
        while curr:
            # If no left child, move to right
            if not curr.left:
                curr = curr.right
            else:
                # Find rightmost node in left subtree
                pred = curr.left
                while pred.right:
                    pred = pred.right

                # Rewire: left subtree to right, original right to end
                pred.right = curr.right
                curr.right = curr.left
                curr.left = None
                # Move to next node (former left)
                curr = curr.right

• Line 4: Start with curr at root.
• Line 7-19: Loop over nodes:
• Line 9-10: No left child, skip to right.
• Line 12-14: Find predecessor (rightmost in left subtree).
• Line 17-18: Link predecessor’s right to current right, move left subtree to right, clear left.
• Line 20: Advance to new right.
• Time Complexity: O(n)—each node visited once.
• Space Complexity: O(1)—no extra space.

This rewires the tree like a pro!

Alternative Solution: Recursive Preorder Traversal

Why an Alternative Approach?

The recursive preorder approach is simpler to grasp—O(n) time, O(n) space via the call stack. It collects the preorder sequence implicitly and flattens as it unwinds. It’s like writing down the order first, then relinking—intuitive but less space-efficient.

How It Works

Here’s the plan:

• Step 1: Use recursion to process preorder (root, left, right).
• Step 2: Track the previous node globally.
• Step 3: Link each node’s right to the next, set left to None.

Step-by-Step Example

Example: root = [1, 2, 5, 3, 4, None, 6]

• Preorder: 1, 2, 3, 4, 5, 6.
• Recursion:
• 1: prev = None, link to 2, prev = 1.
• 2: Link to 3, prev = 2.
• 3: Link to 4, prev = 3.
• 4: Link to 5, prev = 4.
• 5: Link to 6, prev = 5.
• 6: Done.
• Result: [1, None, 2, None, 3, None, 4, None, 5, None, 6].

Code for Recursive Approach

Copy codeclass Solution:
    def __init__(self):
        self.prev = None

    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return

        # Store right child (will process later)
        right = root.right

        # Link previous to current, clear left
        if self.prev:
            self.prev.right = root
            self.prev.left = None
        self.prev = root

        # Recurse on left, then right
        self.flatten(root.left)
        self.flatten(right)

• Line 3-4: Global prev to track last node.
• Line 8-18: Recursive function:
• Line 11: Save right child.
• Line 14-15: Link prev to current, update prev.
• Line 18-19: Process left, then right.
• Time Complexity: O(n)—each node visited once.
• Space Complexity: O(n)—recursion stack.

It’s a recursive chain builder!

Comparing the Two Solutions

• Morris-like (Best):
• Pros: O(n) time, O(1) space, in-place magic.
• Cons: Trickier to follow.
• Recursive (Alternative):
• Pros: O(n) time, O(n) space, simpler logic.
• Cons: Uses stack space.

Morris-like wins for efficiency.

Additional Examples and Edge Cases

• [1, 2]: [1, None, 2].
• [1, None, 2]: [1, None, 2].
• []: [].

Both handle these seamlessly.

Complexity Breakdown

• Morris-like: Time O(n), Space O(1).
• Recursive: Time O(n), Space O(n).

Morris-like is leaner.

Key Takeaways

• Morris-like: Rewire with no space!
• Recursive: Preorder with ease!
• In-Place: Pointer play is key.
• Python Tip: Classes help globals—see [Python Basics](/python/basics).

Final Thoughts: Straighten That Tree

LeetCode 114: Flatten Binary Tree to Linked List in Python is a tree-twisting treat. The Morris-like approach dazzles with O(1) space, while recursive preorder offers clarity. Want more tree fun? Try LeetCode 94: Binary Tree Inorder Traversal or LeetCode 102: Binary Tree Level Order Traversal. Ready to flatten? Head to Solve LeetCode 114 on LeetCode and reshape that tree today!