Flatten Binary Tree to Linked List
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. Pre-order means root, then left subtree, then right subtree.
The difficulty is doing this restructuring without losing access to subtrees while rewiring pointers. Setting node.right = node.left directly discards the original right subtree before we have visited it. The whole problem is about preserving that right subtree until it has been linked in.
Key Constraints:
Number of nodes in range [0, 2000]: With at most 2,000 nodes, even an O(n^2) solution runs in time, so the work is getting the pointer manipulation correct rather than minimizing operations.- The tree can be empty (0 nodes), so the code must handle a null root.
Node values are irrelevant to the logic. We are rearranging pointers, not reading values.
Approach 1: Pre-order Traversal with List
Intuition
A pre-order traversal visits the nodes in exactly the order they must appear in the flattened list. If we collect every node into a list during that traversal, we already have the final ordering. The second pass walks the list and rewires each node so its left is null and its right points to the next node.
This separates the two concerns. The traversal decides the order, and the rewiring never has to worry about losing a subtree because the list already holds a reference to every node. The cost is O(n) extra space for the list.
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 adds O(h) where h is the height of the tree (O(n) for a skewed tree), but the list already accounts for the O(n) term.
The next approach removes the explicit list by rewiring pointers during the traversal itself.
Approach 2: Reverse Post-order (Recursive)
Intuition
If we process the tree in reverse pre-order (right subtree, then left subtree, then root), the order in which nodes are processed is exactly the reverse of the flattened list. We keep a running pointer prev that holds the previously processed node, which is the node that should come right after the current one. When we process the current node, we set current.right = prev, set current.left = null, then update prev = current.
The ordering is what makes this safe. Pre-order is root, left subtree, right subtree. Reversing it gives right subtree, left subtree, root. The first node processed is the last node of the flattened list, and the last node processed (the root) is the first. Because every node's successor is processed before the node itself, prev always holds the correct next pointer by the time we wire the current node.
This is the same construction as building a singly linked list by prepending. Insert elements in reverse order and the list reads forward correctly, with no need to track a tail pointer. Here prev plays the role of the list head: each node is prepended by pointing its right at the current head and then becoming the new head.
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 removes the list but still uses O(h) stack space from recursion. The next approach flattens the tree iteratively in O(1) space.
Approach 3: Morris Traversal (Iterative, O(1) Space)
Intuition
This is the approach the follow-up asks for. It adapts Morris traversal, which walks a tree without recursion or a stack by temporarily rewiring pointers.
For each node that has a left subtree, the entire left subtree has to move to the right side. Overwriting node.right directly would discard the original right subtree. The fix is to attach the original right subtree to the end of the left subtree before moving anything: find the rightmost node of the left subtree and point its right at the original right subtree. After that, moving the left subtree into node.right keeps every node reachable, because walking to the end of the relocated left subtree leads straight into the old right subtree.
The pre-order property follows from this. After the move, node.right is the old left subtree (the nodes that come next in pre-order), and the old right subtree hangs off the rightmost end of it (the nodes that come after the entire left subtree). Advancing current down the right pointers then revisits each node and repeats the same fix where needed.
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.