Flatten Binary Tree to Linked List: In-Place Preorder

You are given the root of a binary tree. Flatten it into a "linked list" in-place: every node's left pointer should be null, and every node's right pointer should point to the next node in preorder traversal.

This is LeetCode 114: Flatten Binary Tree to Linked List, and it is one of those problems where the naive solution works fine but the truly elegant approach teaches you something deep about tree pointer manipulation.

The trick? You can do it in O(1) extra space by rewiring pointers as you walk, similar to a Morris traversal. No stack, no recursion, no extra list. Just careful pointer surgery on the tree itself.

Why this problem matters

Flattening a binary tree to a linked list tests whether you can manipulate tree pointers without losing nodes. It is easy to accidentally orphan an entire subtree by overwriting a pointer before saving the reference. That same skill (careful pointer rewiring) shows up in linked list reversal, tree rotation, and many other interview problems.

The problem also has a beautiful O(1) space solution that most people never see. Understanding it gives you a reusable trick: if a node has a left subtree, you can graft the right subtree onto the end of the left subtree, then move the left subtree to the right. No extra storage needed.

The key insight

Preorder traversal visits root, then left subtree, then right subtree. So in the flattened list, the left subtree's nodes come right after the current node, and the right subtree's nodes come after the entire left subtree.

That means: if we find the rightmost node of the left subtree (the last node visited in the left subtree's preorder), we can attach the right subtree there. Then we move the left subtree to the right side and clear the left pointer. Now the current node is done, and we just move to the next right node and repeat.

This is the same "find the predecessor" idea used in Morris traversal.

Approach 1: Recursive (postorder)

The cleanest recursive solution works in reverse. If you flatten the right subtree first, then the left subtree, you can stitch them together without losing any references.

def flatten(root):
    """Flatten tree to linked list in-place."""
    prev = [None]  # mutable container for closure

    def helper(node):
        if node is None:
            return
        helper(node.right)    # flatten right first
        helper(node.left)     # then left
        node.right = prev[0]  # point right to previously processed node
        node.left = None      # clear left
        prev[0] = node        # this node is now the previous

    helper(root)

This is a reverse postorder traversal (right, left, root). We process the tree from the back of the preorder sequence to the front. At each node, we set node.right to whatever we processed last, and clear node.left. The prev list holds our running "next node" pointer.

Why does this work? Consider the preorder sequence [1, 2, 3, 4, 5, 6]. If we process it in reverse order [6, 5, 4, 3, 2, 1], then at each step we just need to point node.right to the node we handled in the previous step.

Time: O(n). We visit every node once. Space: O(h) for the recursion stack, where h is the tree height.

Approach 2: Iterative with a stack

If you want to avoid recursion, you can use an explicit stack to simulate the preorder traversal. Process each node by saving its right child, moving the left child to the right, and pushing children onto the stack in the correct order.

def flatten(root):
    """Flatten tree to linked list using a stack."""
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
        if stack:
            node.right = stack[-1]  # next node in preorder
        node.left = None

The stack gives us preorder traversal. We push right first, then left, so left gets popped first (LIFO). After popping a node, whatever is on top of the stack is the next node in preorder, so we set node.right to that. Then we clear node.left.

Time: O(n). Space: O(n) worst case for the stack (when the tree is a complete binary tree).

Approach 3: O(1) space (Morris-like)

This is the real gem. No recursion, no stack, just a while loop and pointer rewiring.

def flatten(root):
    """Flatten tree to linked list in O(1) space."""
    curr = root
    while curr:
        if curr.left:
            # Find the rightmost node of the left subtree
            predecessor = curr.left
            while predecessor.right:
                predecessor = predecessor.right

            # Graft curr's right subtree after the predecessor
            predecessor.right = curr.right
            # Move the left subtree to the right
            curr.right = curr.left
            curr.left = None

        # Move to the next node
        curr = curr.right

Here is the logic step by step:

1. Start at the root.
2. If the current node has no left child, just move right.
3. If it does have a left child, find the rightmost node of the left subtree. This is the predecessor, the node that comes just before the right subtree in preorder.
4. Set predecessor.right = curr.right. This grafts the right subtree onto the end of the left subtree.
5. Set curr.right = curr.left and curr.left = None. This moves the left subtree to the right side.
6. Move curr = curr.right and repeat.

Time: O(n). Each node is visited at most twice (once as curr, once while finding a predecessor). Space: O(1). No stack, no recursion, no extra data structures.

Visual walkthrough

Let's trace the O(1) space algorithm through the tree [1, 2, 5, 3, 4, null, 6]. Watch how the pointers get rewired at each step.

The pattern is always the same: find the predecessor, graft the right subtree there, move the left subtree to the right, advance. After each rewiring, the current node has no left child and we can safely move right.

Complexity analysis

All three approaches are O(n) time. The difference is in space. The recursive solution uses O(h) stack space where h is the tree height (O(log n) for balanced, O(n) for skewed). The iterative stack solution can hold up to O(n) nodes. The Morris-like solution uses only a few pointer variables, so it is true O(1) space.

For interviews, the recursive approach is usually the fastest to write. But if the interviewer asks "can you do it in O(1) space?", the Morris-like approach is the answer.

Edge cases to watch for

• Empty tree (root is None): return immediately. All three solutions handle this.
• Single node (no children): already a valid linked list. No work needed.
• Left-skewed tree (every node only has a left child): the Morris-like approach moves each left child to the right, one by one. Each step processes one node.
• Right-skewed tree (every node only has a right child): already flat. The Morris-like approach just walks right without any rewiring.
• Tree with only right children and one left leaf: make sure you do not lose the right subtree when grafting.

The building blocks

This problem uses one key building block:

Pre-order state passing (pre-order-state-passing). The flatten operation processes nodes in preorder (root, left, right). At each node, we do structural work (rewiring pointers) before moving to the next node. In the Morris-like approach, the "state" is implicit in the tree structure itself: we modify the tree as we go so that the next right pointer always leads to the correct next node in preorder.

# The general pre-order-state-passing pattern:
def solve(node):
    if node is None:
        return
    # do work at current node   # process
    solve(node.left)            # go left
    solve(node.right)           # go right

For Flatten Binary Tree, "do work" means rewiring pointers so the left subtree becomes the right child and the original right subtree gets grafted at the end. The recursive version flips the order (right, left, root) to process in reverse, which makes the stitching simpler.

From understanding to recall

You just traced through three different approaches and watched the pointer manipulation in detail. You can see why it works. But could you write the O(1) space version from scratch in an interview without looking at it?

Understanding is not recall. Recognizing the solution when you read it is very different from producing it under pressure. The pre-order-state-passing building block (process the current node, then handle children) appears in problem after problem. If you drill it in isolation, you can snap it into place whenever a new tree problem asks for it.

Spaced repetition helps you bridge that gap. You practice writing the solution from memory at increasing intervals. After a few reps, the pattern of "find predecessor, graft right subtree, move left to right, advance" becomes second nature.

Related posts

• Trees (Data Structure Overview) - Understand the fundamentals of binary trees, traversal orders, and recursive structure
• Invert Binary Tree - Another in-place tree transformation that uses the same pre-order traversal skeleton
• Construct Binary Tree from Preorder and Inorder Traversal - Another problem that depends on deep understanding of preorder traversal and pointer manipulation