L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Java

Transforming a binary tree into a flattened, linked-list-like structure in-place (following a pre-order traversal sequence) without allocating external nodes or data structures.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given a binary tree, the goal is to flatten it into a "linked list" where the linked list's right pointers point to the next node in the pre-order traversal sequence, and all left pointers are set to null.

The Naive Trap

A beginner might think: "Let's just perform a pre-order traversal, collect all node values into a list or create brand new nodes, and build a fresh linked list."

Note: This violates the core constraints of the problem. You cannot allocate an external linked list or create new nodes. You must rearrange the existing pointers of the given tree in-place.

When successfully flattened, the tree structure should look like this:

2. Core Mental Model & Real-Life Analogy

The Rewiring Challenge

Imagine you have a physical set of train cars (nodes) linked together in a complex railroad junction (binary tree). You are not allowed to disassemble the cars or build a new train yard. You must walk along the tracks, disconnect specific couplings, and reconnect them end-to-end so that every car's main coupling (right) points strictly to the immediate next car in pre-order sequence, while side tracks (left) are permanently unhooked (null).

3. Approach 1: Recursive Solution (Reverse Post-Order)

The Intuition

Instead of attacking the root first (standard pre-order), what if we process the tree backward? If we traverse in a Reverse Post-Order fashion (Right -> Left -> Root), we can visit the tail end of our desired linked list first (e.g., node 7, then 6, 5, etc.).

By keeping track of the previous node we just processed, we can simply point the current node's right pointer to previous, set its left pointer to null, and update previous to the current node.

Step-by-Step Recursive Walkthrough

1. Initialize previous = null.
2. Recursively call the function on node.right.
3. Recursively call the function on node.left.
4. Point node.right = previous.
5. Point node.left = null.
6. Update previous = node.

Code Implementation (Recursive)

class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null) return;

        // Traverse Right then Left (Reverse Post-Order)
        flatten(root.right);
        flatten(root.left);

        // Rewiring current node
        root.right = prev;
        root.left = null;
        
        // Update previous to current node
        prev = root;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ where $N$ is the number of nodes, as we visit each node exactly once.
• Space Complexity: $\mathcal{O}(N)$ in the worst-case scenario due to the recursive call stack (skewed tree).

4. Approach 2: Iterative Solution Using a Stack

The Intuition

Recursion uses the implicit system call stack. We can make this explicit by utilizing an explicit Stack data structure. Because a stack operates on Last-In-First-Out (LIFO) principles, if we want to process nodes in pre-order (Root -> Left -> Right), we must push the Right child first and then the Left child into the stack. This ensures the left child is popped and processed first.

Step-by-Stack Workflow

1. Push the root node into the stack.
2. While the stack is not empty:
   • Pop the top node (curr).
   • If curr.right exists, push it to the stack.
   • If curr.left exists, push it to the stack.
   • If the stack is not empty, peek at the new top of the stack and set curr.right = stack.peek().
   • Set curr.left = null.

Code Implementation (Stack-Based)

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            
            if (curr.right != null) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
            
            if (!stack.isEmpty()) {
                curr.right = stack.peek();
            }
            curr.left = null;
        }
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ as every node is pushed and popped from the stack once.
• Space Complexity: $\mathcal{O}(N)$ to store nodes in the stack.

5. Approach 3: Morris Traversal (Optimal $\mathcal{O}(1)$ Space)

The Intuition

Can we solve this without allocating stack or recursion space ($\mathcal{O}(1)$ auxiliary space)? Yes, using Morris Traversal principles.

Look at the pre-order relationship:

In a flattened pre-order list, the entire left subtree is inserted right after the root, and the original right subtree comes immediately after the rightmost node of the left subtree.

To link this properly:

1. Find the rightmost node of the current node's left subtree (in this case, node 4).
2. Connect that rightmost node's right pointer to the current node's original right child (5).
3. Move the entire left subtree to the current node's right.
4. Set the current node's left to null.
5. Advance current to current.right.

Step-by-Step Execution Flow

Code Implementation (Morris Traversal / $\mathcal{O}(1)$ Space)

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        
        while (curr != null) {
            if (curr.left != null) {
                // Find the rightmost node of the left subtree
                TreeNode prev = curr.left;
                while (prev.right != null) {
                    prev = prev.right;
                }
                
                // Rewire: connect left subtree's rightmost to current's right
                prev.right = curr.right;
                
                // Move left subtree to the right
                curr.right = curr.left;
                curr.left = null;
            }
            // Move on to the next node on the right
            curr = curr.right;
        }
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$. Each node is visited, and finding the rightmost predecessor takes proportional time, but across the entire tree, edges are traversed a constant number of times (amortized $\mathcal{O}(N)$).
• Space Complexity: $\mathcal{O}(1)$ auxiliary space. No stack or recursion overhead is used.

6. Comparative Synthesis of Approaches

7. Summary and Key Takeaways

• Problem Objective: Flatten a binary tree into a linked list in-place matching pre-order traversal sequence (right pointers link nodes, left pointers are null).
• Constraint Enforcement: No external node allocation or auxiliary lists are permitted; tree pointers must be rearranged directly.
• Recursive Insight: Traversing in a Reverse Post-Order (Right -> Left -> Root) allows us to track the previous processed node and wire pointers backward effortlessly.
• Stack-Based Extension: Pushing the right child first and then the left child ensures the left child is popped first, maintaining the correct pre-order sequence.
• Optimal Morris Approach: Finding the rightmost node of the left subtree allows us to bridge the gap between the left subtree and the right subtree in $\mathbf{\mathcal{O}(1)}$ space.