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

text
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.

Core Insight for Flatten Binary Tree to Linked List

The key to solving LeetCode 114 in-place lies in trusting the recursive function (the "leap of faith").

If we assume our flatten function works correctly, then calling flatten(root.left) will turn the left subtree into a straight line (linked list), and flatten(root.right) will turn the right subtree into a straight line.

Once the subtrees are flattened, the problem reduces to a simple pointer rewiring operation at the current root:

1. Disconnect the root.right (the flattened right subtree).
2. Move the root.left (the flattened left subtree) to become the new root.right.
3. Traverse to the very end of this new root.right chain.
4. Attach the originally disconnected right subtree to the end of that chain.
5. Ensure root.left is set to null to satisfy the constraints.

This logic maintains the pre-order invariant: Root is processed, followed immediately by the entire Left subtree (now on the right), followed by the entire Right subtree.

Visual Description: Imagine the recursion tree at a specific node. The left child represents a processed chain. We essentially "insert" the entire left chain between the node and its right child. We then perform this same logic for every node in the tree, working from the bottom up (post-order logic) or top-down depending on implementation, though the structural result aligns with pre-order.

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.

Reference Implementation

C++ Solution for LeetCode 114

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        
        // Recursively flatten the subtrees
        flatten(root->left);
        flatten(root->right);
        
        // If there is a left child, we need to insert it
        if (root->left) {
            // Store the original right subtree
            TreeNode* tempRight = root->right;
            
            // Move left subtree to right
            root->right = root->left;
            root->left = nullptr; // Important: ensure left is null
            
            // Find the end of the new right subtree (old left subtree)
            TreeNode* current = root;
            while (current->right) {
                current = current->right;
            }
            
            // Attach the original right subtree
            current->right = tempRight;
        }
    }
};

Java Solution for LeetCode 114

java
/**
 * Definition for a binary tree node.
 * public 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) {
        if (root == null) return;
        
        // Recursively flatten left and right subtrees
        flatten(root.left);
        flatten(root.right);
        
        // Post-order processing: Rewire connections
        if (root.left != null) {
            // Save the current right child
            TreeNode tempRight = root.right;
            
            // Move the left child to the right
            root.right = root.left;
            root.left = null; // Don't forget to null out the left pointer
            
            // Traverse to the end of the new right chain
            TreeNode current = root;
            while (current.right != null) {
                current = current.right;
            }
            
            // Attach the saved right child to the end
            current.right = tempRight;
        }
    }
}

Python Solution for LeetCode 114

python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        
        # Recursively flatten the subtrees
        self.flatten(root.left)
        self.flatten(root.right)
        
        # If there is a left child, insert it between root and right
        if root.left:
            temp_right = root.right
            
            # Move left subtree to right
            root.right = root.left
            root.left = None
            
            # Find the tail of the new right subtree
            current = root
            while current.right:
                current = current.right
            
            # Attach the original right subtree
            current.right = temp_right