Flatten Binary Tree to Linked List

LeetCode 114: Flatten Binary Tree to Linked List Solution & Explanation

Problem Overview

TL;DR: Recursively flatten the left and right subtrees, then graft the flattened left subtree between the root and the flattened right subtree.

The problem requires transforming a binary tree into a specific type of "linked list" in-place. While the structure uses the TreeNode class, the resulting topology must be a single chain of nodes following the pre-order traversal sequence (Root $\to$ Left $\to$ Right). In this flattened state, all left pointers must be null, and right pointers act as the next pointers of a linked list. This is a popular interview question that tests your ability to manipulate pointer references within a recursive structure, specifically targeting LeetCode 114.

Brute Force Approach for Flatten Binary Tree to Linked List

The most straightforward way to solve this is to ignore the "in-place" preference initially and focus on the output requirement: a pre-order sequence.

1. Traverse: Perform a standard recursive pre-order traversal (Root, Left, Right) on the tree.
2. Store: Collect all nodes in a list or array as they are visited.
3. Relink: Iterate through the collected list of nodes. For every node current at index i, set current.left to null and current.right to the node at index i+1.

Naive Pseudo-code

function flatten(root):
    list = []
    preorder(root, list)
    
    for i from 0 to list.length - 2:
        list[i].left = null
        list[i].right = list[i+1]
        
    list[last].left = null
    list[last].right = null

Analysis

• Time Complexity: $O(N)$, where $N$ is the number of nodes. We visit each node to store it and again to link it.
• Space Complexity: $O(N)$ to store the list of nodes.
• Why it fails: While this produces the correct structure, it violates the spirit of the problem (and the follow-up constraint) which asks for an in-place modification using $O(1)$ extra space (excluding the recursion stack). It essentially rebuilds the tree rather than rearranging it.

Algorithm Strategy: Tree DFS - Recursive Preorder Traversal

We will implement a recursive DFS function.

1. Base Case: If the current node is null, return immediately.
2. Recursive Step:
   • Recursively call the flatten function on the left child.
   • Recursively call the flatten function on the right child.
   • Note: By the time these return, we assume the left and right subtrees are already flattened linked lists.
3. Rewiring Logic (Post-Order Processing):
   • If the current node has a left child:
     • Store the current right child in a temporary variable tempRight.
     • Move the left child to root.right.
     • Set root.left to null.
     • Find the "tail" (the last node) of the current root.right (which was the old left subtree).
     • Connect the tempRight to this tail.

This approach modifies the tree structure in place without allocating new nodes.

Execution Flow

Let's trace the algorithm on a simple tree: Root(1), Left(2), Right(5).

1. Call flatten(1).
2. Recurse Left: Call flatten(2).
   • Node 2 is a leaf (assuming simplified tree).
   • flatten(2.left) returns.
   • flatten(2.right) returns.
   • No left child to process. Function returns.
   • Subtree at 2 is now: 2 -> null.
3. Recurse Right: Call flatten(5).
   • Node 5 is a leaf.
   • Returns.
   • Subtree at 5 is now: 5 -> null.
4. Process Root(1):
   • Left child exists (Node 2).
   • Store tempRight = Node 5.
   • Set 1.right = Node 2.
   • Set 1.left = null.
   • Current state: 1 -> 2. Node 5 is detached in tempRight.
   • Find tail of 1.right. We traverse from 1 to 2. Tail is 2.
   • Set tail.right (2.right) = tempRight (5).
   • Final state: 1 -> 2 -> 5.
5. The tree is now a linked list matching the pre-order traversal [1, 2, 5].

Proof of Correctness

The correctness is based on structural induction.

• Base Case: A leaf node is already a flattened list of length 1.
• Inductive Hypothesis: Assume flatten(root.left) and flatten(root.right) correctly produce flattened lists corresponding to the pre-order traversal of the left and right subtrees, respectively.
• Inductive Step: The algorithm rewires pointers such that root.right points to the head of the flattened left subtree, and the tail of that subtree points to the head of the flattened right subtree. The sequence becomes: Root -> Left Subtree (Preorder) -> Right Subtree (Preorder). This matches the definition of a pre-order traversal for the entire tree.

Pattern Reuse Notes

The Tree DFS pattern is fundamental. Understanding the recursive "leap of faith" logic used in LeetCode 114 is directly applicable to:

• LeetCode 100: Same Tree - Uses synchronized DFS on two trees simultaneously.
• LeetCode 101: Symmetric Tree - Uses DFS to compare left and right subtrees as mirror images.
• LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal - Uses DFS to rebuild structure based on traversal constraints.
• LeetCode 226: Invert Binary Tree - Uses DFS to swap left and right children at every node (very similar to the "splice" logic here).

Reference Implementation

C++ Solution for LeetCode 114

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    void flatten(TreeNode* root) {
15        if (!root) return;
16        
17        // Recursively flatten the subtrees
18        flatten(root->left);
19        flatten(root->right);
20        
21        // If there is a left child, we need to insert it
22        if (root->left) {
23            // Store the original right subtree
24            TreeNode* tempRight = root->right;
25            
26            // Move left subtree to right
27            root->right = root->left;
28            root->left = nullptr; // Important: ensure left is null
29            
30            // Find the end of the new right subtree (old left subtree)
31            TreeNode* current = root;
32            while (current->right) {
33                current = current->right;
34            }
35            
36            // Attach the original right subtree
37            current->right = tempRight;
38        }
39    }
40};

Java Solution for LeetCode 114

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    public void flatten(TreeNode root) {
18        if (root == null) return;
19        
20        // Recursively flatten left and right subtrees
21        flatten(root.left);
22        flatten(root.right);
23        
24        // Post-order processing: Rewire connections
25        if (root.left != null) {
26            // Save the current right child
27            TreeNode tempRight = root.right;
28            
29            // Move the left child to the right
30            root.right = root.left;
31            root.left = null; // Don't forget to null out the left pointer
32            
33            // Traverse to the end of the new right chain
34            TreeNode current = root;
35            while (current.right != null) {
36                current = current.right;
37            }
38            
39            // Attach the saved right child to the end
40            current.right = tempRight;
41        }
42    }
43}

Python Solution for LeetCode 114

1# Definition for a binary tree node.
2# class 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: Optional[TreeNode]) -> None:
10        """
11        Do not return anything, modify root in-place instead.
12        """
13        if not root:
14            return
15        
16        # Recursively flatten the subtrees
17        self.flatten(root.left)
18        self.flatten(root.right)
19        
20        # If there is a left child, insert it between root and right
21        if root.left:
22            temp_right = root.right
23            
24            # Move left subtree to right
25            root.right = root.left
26            root.left = None
27            
28            # Find the tail of the new right subtree
29            current = root
30            while current.right:
31                current = current.right
32            
33            # Attach the original right subtree
34            current.right = temp_right