Flatten Binary Tree to Linked List
Last Updated: March 29, 2026
Understanding the Problem
We need to rearrange a binary tree so that it becomes a right-skewed "linked list" using the existing TreeNode structure. Every node's left child must be null, and its right child must point to the next node in pre-order sequence. The key word here is "pre-order": root, then left subtree, then right subtree.
The real challenge is doing this restructuring without losing access to subtrees as we rewire pointers. If you naively set node.right = node.left, you lose the original right subtree. That tension between rewiring and preserving access is what makes this problem interesting.
Key Constraints:
Number of nodes in range [0, 2000]— With at most 2,000 nodes, any O(n) or even O(n^2) solution runs comfortably. Performance isn't the bottleneck here. The challenge is getting the pointer manipulation right.-100 <= Node.val <= 100— Node values don't affect the logic. We're restructuring the tree, not computing anything from values.- The tree can be empty (0 nodes), so we need to handle the null root case.
Approach 1: Pre-order Traversal with List
Intuition
The most straightforward way to think about this: if we do a pre-order traversal and collect all nodes into a list, we already have them in the correct order. Then we just rewire each node in the list so that its left is null and its right points to the next node.
This is the "just do what the problem says" approach. It's not space-efficient, but it's dead simple and a great starting point in an interview.
Algorithm
- If the root is null, return.
- Perform a pre-order traversal (root, left, right) and store all nodes in a list.
- Iterate through the list. For each node at index i:
- Set
node.left = null. - Set
node.right = list[i + 1](or null for the last node).
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node once during the pre-order traversal, and once more during the rewiring loop. That's 2n operations, which is O(n).
- Space Complexity: O(n). The list stores all n nodes. The recursion stack also uses O(h) space where h is the height of the tree, but the list dominates.
This approach works correctly but uses O(n) extra space for the list. What if we could rewire pointers during traversal instead of collecting all nodes first?
Approach 2: Reverse Post-order (Recursive)
Intuition
Here's a clever observation. If we process the tree in reverse pre-order (right subtree, then left subtree, then root), the last node we process is the first node of the flattened list. So we can keep a running pointer called prev that tracks the previously processed node. When we visit the current node, we set current.right = prev and current.left = null, then update prev = current.
Why does this work? In pre-order, the sequence is: root, left subtree, right subtree. If we reverse that, we get: right subtree, left subtree, root. So the very first node we process is the rightmost leaf (last in the flattened list), and the very last node we process is the root (first in the flattened list). By maintaining prev, each node already knows what comes after it.
The magic is in the processing order. By going right-left-root, we guarantee that when we process any node, everything that should follow it in the flattened list is already linked together and accessible through prev. We're essentially building the linked list backwards, one node at a time.
This is the same idea behind building a linked list by prepending: if you add elements in reverse order, you end up with the correct forward order without needing to track the tail.
Algorithm
- Initialize a variable
prevto null. - Define a recursive function that processes each node:
- If node is null, return.
- Recurse on
node.rightfirst. - Recurse on
node.left. - Set
node.right = prevandnode.left = null. - Update
prev = node. - Call the function on root.
Example Walkthrough
Code
- Time Complexity: O(n). Every node is visited exactly once during the recursion.
- Space Complexity: O(h). Where h is the height of the tree, due to the recursion stack. In the worst case (skewed tree), h = n, so this is O(n). For a balanced tree, h = log n.
This approach eliminates the extra list but still uses O(h) stack space from recursion. Can we flatten the tree without any extra space at all?
Approach 3: Morris Traversal (Iterative, O(1) Space)
Intuition
This is the approach the follow-up is hinting at. The core idea comes from Morris traversal, which lets you traverse a tree without recursion or a stack by temporarily modifying the tree structure.
Here's the key insight: for each node, if it has a left subtree, we need to move that entire left subtree to the right. But we can't just overwrite node.right because we'd lose the original right subtree. So before moving anything, we find the rightmost node of the left subtree and connect it to the original right subtree. This way, when we later traverse down the (now right-shifted) left subtree, we'll eventually reach the original right subtree.
Think of it like reorganizing a filing cabinet. Before you move a folder from the left drawer to the right drawer, you first make sure the last item in that folder has a note pointing to whatever was originally in the right drawer. That way nothing gets lost.
Algorithm
- Start with
current = root. - While
currentis not null: - If
currenthas a left child:
a. Find the rightmost node of the left subtree (call it predecessor).
b. Set predecessor.right = current.right (stitch the right subtree).
c. Set current.right = current.left (move left subtree to the right).
d. Set current.left = null (clear the left pointer).
- Move to
current = current.right.
Example Walkthrough
Code
- Time Complexity: O(n). Each node is visited at most twice: once by the outer loop and at most once as part of the "find rightmost" traversal. The total number of pointer moves across all iterations is bounded by 2n.
- Space Complexity: O(1). No recursion, no stack, no extra data structures. We only use a constant number of pointer variables.