Flatten Binary Tree to Linked List

The dangerous line in this problem is also the tempting one:

current.right = current.left

It places the left subtree in the correct position, but it can disconnect the original right subtree. The real task is to move the left subtree in front of the right subtree without losing the displaced structure.

Read the contract: preorder becomes the right spine

The tree must be modified in place using its existing TreeNode objects:

• Every node must end with left = None.
• Each right pointer must point to the next node.
• The order must match the original preorder traversal: root, left subtree, right subtree.
• No separate linked-list nodes are created.

For this tree:

        1
       / \
      2   5
     / \   \
    3   4   6

The preorder sequence is:

1, 2, 3, 4, 5, 6

The flattened structure must therefore be:

1 → 2 → 3 → 4 → 5 → 6

Every arrow is a right pointer. Every left pointer is None.

The node values are irrelevant to the algorithm. This is a pointer-structure problem: the tree may be empty, and the constraints allow up to 2,000 nodes, but no value comparisons are needed.

Recognize the preorder signal

For a current node current, preorder requires this order:

current → all of current.left → all of current.right

That gives three local obligations:

1. The left subtree must become the immediate continuation after current.
2. The original right subtree must remain reachable after the entire left subtree.
3. current.left must be cleared.

Think of the original right subtree as a section of track that has been displaced. Moving the left subtree onto the right-pointer path is safe only if that displaced section is connected somewhere first.

Start with the simpler baselines

The constant-space method is easier to derive after separating ordering from storage.

Collect preorder nodes first

One straightforward approach is:

1. Collect every node in preorder.
2. Connect each node to the next with right.
3. Set every left pointer to None.

This uses O(n) auxiliary space for the node list.

Use recursion

You can also recursively flatten the left and right subtrees, then connect the resulting chains:

1. Flatten the left subtree.
2. Flatten the right subtree.
3. Put the flattened left chain after the current node.
4. Append the flattened right chain after it.

This uses O(h) call-stack space, where h is the tree height. A highly skewed tree can make h equal to n.

Use an explicit preorder stack

An iterative preorder traversal can push the right child first and the left child second. The stack then remembers which node should be visited next.

This uses O(n) space in the worst case.

These approaches all preserve the order by remembering pending nodes externally. The in-place solution removes that external memory by using the tree's existing pointers as temporary structure.

Derive the in-place splice

Walk through the evolving right spine with a pointer called current.

For each current:

• If it has no left child, its next node is already current.right.
• If it has a left child, the left subtree must be moved in front of the original right subtree.

Let predecessor be the rightmost node on the current rightward path inside current.left.

This description matters. predecessor is a splice point; it is not necessarily the final node visited by preorder in the left subtree at that moment. It may still have a left subtree that later needs to be moved in front of the original right subtree.

The rewiring is:

predecessor.right = current.right
current.right = current.left
current.left = None

In words:

1. Save the original right subtree by attaching it to predecessor.
2. Move the left subtree into current.right.
3. Clear current.left.

The first assignment must happen before overwriting current.right.

current
├── left subtree
└── original right subtree

becomes

current → left subtree → original right subtree

The algorithm does not copy nodes. It changes the links between existing nodes.

Failure mode: assigning current.right = current.left without first saving the original right subtree can make that subtree unreachable. Preserve the displaced pointer before overwriting it.

Why the rightmost node is the splice point

Suppose the current structure is:

current
├── L
└── R

Preorder requires every node in L before every node in R.

Following right pointers from L reaches the current end of that path. Attaching R there places R after the visible rightward portion of L. If that endpoint still has a left child, a later loop iteration processes that node and moves its left subtree in front of the attached R.

So the algorithm does not assume that the splice point is already the final preorder node of L. Instead, it preserves the remaining structure so subsequent iterations can expose it in the required order.

Maintain a correctness invariant

Use this invariant:

At the start of each loop iteration, every node before current on the right spine is already arranged in original preorder, has a null left pointer, and remains connected to every unprocessed node.

Now examine the two cases.

current.left is empty

There is no left subtree to place before the right subtree. The next preorder node is already current.right.

Advancing to current.right leaves the processed prefix unchanged and keeps the unprocessed remainder connected.

current.left exists

Let predecessor be the rightmost node reached by following right pointers from current.left.

First, attach the original right subtree:

predecessor.right = current.right

The original right subtree is now preserved.

Next, move the left subtree into the position immediately after current:

current.right = current.left
current.left = None

This establishes the local preorder order:

current → left subtree → original right subtree

If a node inside the moved left subtree still has a left child, that branch remains reachable. A later iteration will process it and perform the same local transformation. Thus, the algorithm gradually converts the entire structure rather than pretending one splice finishes all work at once.

No node is created or duplicated. No subtree is discarded because the original right pointer is attached before it is overwritten. When the loop finishes, every node is on the right spine, every left pointer is null, and the order is preorder.

Dry-run: track the actual pointer state

Start with:

        1
       / \
      2   5
     / \   \
    3   4   6

Process node 1

The rightmost node reached from 1.left is 4.

Before rewiring:

1.left  = 2
1.right = 5
4.right = None

Apply the assignments:

4.right = 5
1.right = 2
1.left = None

The structure becomes:

1
 \
  2
 / \
3   4
     \
      5
       \
        6

At this point, the right-only path is:

1 → 2 → 4 → 5 → 6

Node 3 is still pending through 2.left. This distinction is exactly why the predecessor explanation must be precise: node 4 was the rightmost node on the current rightward path, but node 3 still has to be moved before it.

Process node 2

Node 2 has a left child. Its predecessor is 3.

Apply:

3.right = 4
2.right = 3
2.left = None

Now the right-only path is:

1 → 2 → 3 → 4 → 5 → 6

Process nodes 3, 4, 5, and 6

None of these nodes has a left child. The algorithm simply advances through their right pointers.

The final structure is:

1 → 2 → 3 → 4 → 5 → 6

with every left pointer set to None.

The broken version fails at the first operation:

current.right = current.left

After that assignment, node 5 is no longer reachable unless it was saved or attached elsewhere first. Pointer mutation is unforgiving: once the only path to a subtree is overwritten, the subtree has disappeared from the reachable structure.

Flatten Binary Tree to Linked List: Python solution

Assume the platform provides the standard TreeNode class.

class Solution:
    def flatten(self, root: TreeNode | None) -> None:
        current = root

        while current is not None:
            if current.left is not None:
                # Find the rightmost node on the left subtree's
                # current rightward path.
                predecessor = current.left

                while predecessor.right is not None:
                    predecessor = predecessor.right

                # Preserve the original right subtree first.
                predecessor.right = current.right

                # Move the left subtree into the right position.
                current.right = current.left
                current.left = None

            current = current.right

Each variable has a specific obligation:

• current identifies the node whose local structure is being repaired.
• predecessor identifies where the original right subtree must be attached.
• current.right becomes the next part of the evolving preorder chain.

The empty-tree case needs no separate branch. If root is None, the loop does not execute.

For local testing, inspect only the right pointers:

def right_chain(root: TreeNode | None) -> list[int]:
    values = []

    while root is not None:
        values.append(root.val)
        assert root.left is None
        root = root.right

    return values

For the example tree:

[1, 2, 3, 4, 5, 6]

The assertion checks the shape requirement as well as the order. A right-chain traversal can appear correct even when a forgotten left pointer still violates the contract.

Complexity and edge cases

The iterative splice uses:

• Time: O(n)
• Auxiliary space: O(1)

The nested predecessor search deserves attention. It is easy to see a loop inside a loop and conclude O(n²). The searches are amortized across the evolving structure: each search follows right edges through a subtree that is being moved into the main right spine, and those edges are not repeatedly explored as part of the same untouched subtree. Across the entire process, the relevant pointer traversals are bounded linearly by the nodes and edges in the tree.

Important structural cases:

Case	Behavior
Empty tree	The loop does nothing.
Single node	It already satisfies the output shape.
Right-skewed tree	No rewiring is needed; the algorithm advances.
Left-only chain	Each left child is moved to the right.
Root with both children	The left subtree is placed first, and the old right subtree is preserved after it.
Negative or duplicate values	No effect; the algorithm depends only on pointers.

In an interview, verify three things:

1. Every original node appears exactly once.
2. The right-chain order matches the original preorder traversal.
3. Every node has left is None.

The recursive and explicit-stack solutions are useful when extra space is acceptable. The predecessor-splicing method is the correct target when the follow-up requires in-place O(1) extra space.

The transferable rule is this:

When a tree must become a traversal-shaped structure, identify the next required visit, preserve any displaced pointer before overwriting it, and maintain an invariant over the processed prefix.

Do not memorize three assignments in isolation. Name what each pointer protects, trace one branched example, and then derive the splice again when the next tree problem asks you to rearrange structure in place.