Flatten Binary Tree to Linked List

Description

Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a “linked list”:

• The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [0]
Output: [0]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Approach 1: Reverse Postorder DFS ($O(N)$ Time, $O(H)$ Space)

Intuition

Standard Preorder traversal is $\text{Root}\to \text{Left}\to \text{Right}$. If we traverse the tree in Reverse Preorder ($\text{Right}\to \text{Left}\to \text{Root}$), we visit nodes in the exact opposite order of the final linked list:

1. Maintain a global prev pointer initialized to null.
2. Recursively traverse the right subtree first, then the left subtree.
3. For the current node, set node.right = prev and node.left = null.
4. Update prev = node.

class Solution {
    private TreeNode prev = null;
 
    public void flatten(TreeNode root) {
        if (root == null) return;
 
        // Reverse Preorder: Right -> Left -> Root
        flatten(root.right);
        flatten(root.left);
 
        root.right = prev;
        root.left = null;
        prev = root;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Visits every node in the binary tree exactly once.
• Space Complexity: $O(H)$ — Recursion call stack requires space proportional to tree height $H$ ($O(\log N)$ for balanced, $O(N)$ for skewed).

---

Approach 2: Morris-Style Traversal ($O(N)$ Time, $O(1)$ Space)

Intuition

Achieves $O(1)$ auxiliary space by rewiring pointers in-place without recursion or a stack:

1. Iterate through nodes using pointer curr.
2. If curr has a left child:
   • Find the rightmost node (pred) in curr’s left subtree.
   • Attach pred.right to curr.right (reserving the rest of the tree).
   • Shift curr’s left subtree to its right side (curr.right = curr.left), and set curr.left = null.
3. Advance curr = curr.right and repeat until curr == null.

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
 
        while (curr != null) {
            if (curr.left != null) {
                // Find rightmost node of left subtree
                TreeNode pred = curr.left;
                while (pred.right != null) {
                    pred = pred.right;
                }
 
                // Connect rightmost node to original right child
                pred.right = curr.right;
 
                // Splice left subtree into right pointer
                curr.right = curr.left;
                curr.left = null;
            }
            // Advance to next node on right branch
            curr = curr.right;
        }
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each node is visited at most twice (once by curr and once while finding pred).
• Space Complexity: $O(1)$ — Modifies tree in-place without stack or queue memory.

---

Easy Memory Rule

“Reverse Preorder ($\text{Right}\to \text{Left}\to \text{Root}$) using prev pointer $\to$ OR $O(1)$ Morris: Attach curr.right to rightmost node of curr.left, then shift left subtree to right!”