Flatten Binary Tree to Linked List — Solution

Problem

Given the root of a binary tree, reshape it in-place into a flat "linked list" using only the right-child pointers — every node's left pointer should be null, and the right-pointer chain should follow the tree's preorder traversal.

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

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

• Input: root = [1, 2, 5, 3, 4, null, 6]
• Output: [1, null, 2, null, 3, null, 4, null, 5, null, 6]
• Explanation: Preorder visits 1 → 2 → 3 → 4 → 5 → 6, and each node's right pointer forms that chain.

Intuition

A preorder traversal visits a node, then its entire left subtree, then its entire right subtree — exactly the order required by the output. The key insight for the O(1)-space solution is that for any node with a left child, you can find the last node visited in the left subtree (the rightmost node of that subtree), attach the original right subtree there, then pivot the left subtree to the right. This wires the preorder chain one node at a time without collecting anything.

Approach 1 — Preorder Collection

Collect all nodes via preorder traversal into a list, then walk the list and relink each node's right pointer to the next, clearing all left pointers.

1. If root is null, return immediately.
2. Run a recursive preorder traversal, appending each visited node to preorder_nodes.
3. For every consecutive pair (preorder_nodes[i], preorder_nodes[i+1]), set left = null and right = next.
4. Null out the last node's left and right pointers.

1def flatten(self, root: Optional[TreeNode]) -> None:
2    preorder_nodes = []
3
4    def collect(node):
5        if not node:
6            return
7        preorder_nodes.append(node)
8        collect(node.left)
9        collect(node.right)
10
11    collect(root)
12
13    for i in range(len(preorder_nodes) - 1):
14        preorder_nodes[i].left = None
15        preorder_nodes[i].right = preorder_nodes[i + 1]
16
17    if preorder_nodes:
18        preorder_nodes[-1].left = None
19        preorder_nodes[-1].right = None

Time: O(n) — visits every node exactly once.
Space: O(n) — the collection list holds all n nodes, plus O(h) recursion stack.

Approach 2 — Morris-Like In-Place Rewiring

For each node that has a left child, find the rightmost node of that left subtree (the preorder predecessor), wire its right pointer to the current node's right child, then pivot the entire left subtree to the right. No extra storage needed.

1. Set current = root.
2. While current is not null: a. If current.left exists, find predecessor by walking right from current.left until there is no right child. b. Set predecessor.right = current.right — attach the original right subtree to the end of the left subtree. c. Set current.right = current.left and current.left = null — pivot.
3. Advance current = current.right and repeat.

1def flatten(self, root: Optional[TreeNode]) -> None:
2    current = root
3
4    while current:
5        if current.left:
6            # Find the rightmost node of the left subtree (preorder predecessor)
7            predecessor = current.left
8            while predecessor.right:
9                predecessor = predecessor.right
10
11            # Attach the right subtree after the left subtree's last node
12            predecessor.right = current.right
13            # Pivot the left subtree to the right position
14            current.right = current.left
15            current.left = None  # left must be null in the result
16
17        current = current.right

Time: O(n) — each edge is traversed at most twice across all predecessor searches.
Space: O(1) — only a pair of pointers; no recursion stack.

Complexity Summary

Common Mistakes

• Overwriting current.right before saving it — in the Morris approach, if you set current.right = current.left before predecessor.right = current.right, you permanently lose the original right subtree and disconnect the chain.
• Using predecessor.left instead of predecessor.right in the search — the predecessor is the rightmost node of the left subtree, so the search loop must follow right children, not left.
• Forgetting to null out current.left — pivoting left to right and then moving on without clearing current.left leaves illegal left-child pointers in the result.
• Confusing the list with a return value — flatten is void and modifies in-place; the root node does not change, only its children are rewired. Wrapping the result in a new node head is a mistake.
• Not handling the single-node or null root case — the Morris loop exits immediately when current is null, but the preorder-collection approach must guard against preorder_nodes[-1] on an empty list.

Related Problems

• Binary Tree Preorder Traversal — the right-pointer chain in the output is exactly a preorder traversal
• Construct Binary Tree from Preorder and Inorder Traversal — inverse operation: builds a tree from preorder order
• Binary Tree Inorder Traversal — Morris traversal technique applies here for O(1)-space traversal
• Reorder List — similar in-place relinking of nodes in a list structure
• Lowest Common Ancestor of a Binary Tree — preorder tree traversal to locate and process specific nodes