Flatten Binary Tree to Linked List — LC 114 In-Place O(1) Space

Problem Statement#

LeetCode 114 — Flatten Binary Tree to Linked List | Difficulty: Medium

Given the root of a binary tree, flatten the tree into a linked list in-place. The linked list should use the same TreeNode class where right is the next pointer and left is always null. The order must match pre-order traversal.

Constraints:

• The number of nodes is in the range [0, 2000]
• -100 <= Node.val <= 100

Input:  root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Input:  root = []
Output: []

Why This Problem Matters#

Flatten Binary Tree to Linked List is a classic in-place tree manipulation problem asked at Amazon and Microsoft. It tests whether you can restructure a tree without allocating extra memory — a skill relevant to memory-constrained environments. The naive approach (collect nodes in pre-order, then rewire) is O(n) space; interviewers want the O(1) space iterative solution.

The core technique — finding the rightmost node of a subtree and attaching another subtree to it — is the same trick used in Morris traversal. Understanding this problem gives you a foundation for the full Morris in-order traversal algorithm, which itself appears in follow-up interview questions about iterative tree traversal with O(1) space.

The Core Insight#

For each node, the pre-order sequence is: current → left subtree → right subtree. To flatten in-place:

1. Find the rightmost node of the left subtree (the last node visited in the left subtree's pre-order).
2. Attach the current right subtree to that rightmost node's right pointer.
3. Move the entire left subtree to the right.
4. Set the left pointer to null.
5. Advance to node.right and repeat.

This works because after step 3, node.right contains the flattened left subtree, and the original right subtree is now appended at its end — exactly pre-order order.

Visual Dry Run#

Tree: [1, 2, 5, 3, 4, null, 6]

Result: 1 → 2 → 3 → 4 → 5 → 6 (all right pointers, all left=null).

Solution (Optimal)#

class Solution:
    def flatten(self, root) -> None:
        node = root
        while node:
            if node.left:
                # Find the rightmost node in the left subtree
                tail = node.left
                while tail.right:
                    tail = tail.right
 
                # Attach current right subtree after the tail
                tail.right = node.right
 
                # Move left subtree to right
                node.right = node.left
                node.left = None
 
            # Advance to next node (pre-order: now process right child)
            node = node.right

var flatten = function(root) {
    let node = root;
    while (node) {
        if (node.left) {
            // Find rightmost node of left subtree
            let tail = node.left;
            while (tail.right) {
                tail = tail.right;
            }
 
            // Attach current right subtree at tail
            tail.right = node.right;
 
            // Move left subtree to right position
            node.right = node.left;
            node.left = null;
        }
        node = node.right;
    }
};

Time: O(n) — each node visited a constant number of times (at most twice: once as current, once as tail) Space: O(1) — no recursion stack, no extra data structures

Common Mistakes#

• Using O(n) space by collecting all nodes in a list and rewiring — valid but misses the O(1) space insight interviewers want
• Forgetting to set node.left = null after moving the left subtree to the right
• Not finding the rightmost node of the left subtree (just using the left child directly would break the pre-order order)
• Advancing to node.left instead of node.right after the rearrangement
• Recursive approach forgetting to handle the case where the right subtree needs to be attached after recursion

Interview Tips#

• Start by explaining the O(n) space approach (pre-order traversal into a list), then improve to O(1)
• Draw the tail-finding step clearly — interviewers trip candidates up on this detail
• The iterative O(1) solution is what gets you the offer; the recursive solution is acceptable but not optimal
• Mention that this technique is related to Morris traversal

Follow-up Questions#

• How would you do this recursively? Post-order recursion: flatten left, flatten right, then insert flattened-left between root and flattened-right.
• What if you want the list in in-order or post-order? You would need to recurse and rewire pointers differently — the iterative approach is tailored to pre-order specifically.
• How does this relate to Morris traversal? Morris traversal uses the same "find rightmost of left subtree" trick to temporarily thread nodes for O(1) space traversal.
• Can this be done if the tree is not binary? For n-ary trees, you would need to flatten all children chains before stitching them together right-to-left.
• What is the time complexity of the naive recursive approach? Also O(n) but with O(h) space for the call stack.

Key Takeaways#

• Flatten Binary Tree uses the "rightmost of left subtree" pointer as a connection point — the same trick as Morris traversal
• The iterative O(1) space solution processes each node exactly once: find tail, attach right, move left, advance
• Always set node.left = null after moving the left subtree to avoid a corrupted tree
• Pre-order flattening means: current node first, then left subtree, then right subtree
• Time is O(n) and space is O(1) — better than the O(n) space list-based approach
• The tail-finding inner loop looks O(n) per step but amortizes to O(n) total across all iterations
• This problem demonstrates that in-place tree restructuring is always possible by threading pointers carefully