Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Flatten Binary Tree to Linked List

MEDIUMProblemSolveExternal Links

Description

Given the root of a binary tree, flatten the tree into a "linked list" in-place.

The flattened structure must satisfy the following rules:

  • Use the same TreeNode class for the resulting structure.
  • The right child pointer of each node should point to the next node in the flattened list.
  • The left child pointer of every node must be set to null.
  • The ordering of nodes in the flattened list must match the pre-order traversal (root → left subtree → right subtree) of the original binary tree.

The transformation must happen in-place — you should modify the original tree's pointers rather than creating a new data structure.

Binary tree before and after flattening: tree with root 1, left subtree [2,3,4], right subtree [5,6] becomes a right-skewed chain 1→2→3→4→5→6
Binary tree before and after flattening: tree with root 1, left subtree [2,3,4], right subtree [5,6] becomes a right-skewed chain 1→2→3→4→5→6

Examples

Example 1

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

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

Explanation: The original tree has this structure:

      1
     / \
    2   5
   / \   \
  3   4   6

The pre-order traversal visits nodes in the order: 1, 2, 3, 4, 5, 6. After flattening, each node's right pointer points to the next node in this pre-order sequence, and every left pointer is null. The result is a right-skewed chain: 1 → 2 → 3 → 4 → 5 → 6.

Example 2

Input: root = []

Output: []

Explanation: An empty tree has no nodes to flatten. The result is simply an empty tree (null root).

Example 3

Input: root = [0]

Output: [0]

Explanation: A single-node tree is already in flattened form. Node 0 has no left or right children, so no modifications are needed.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is in two separate phases: first figure out the correct order of nodes, then physically rearrange the pointers.

Since the flattened list must follow pre-order traversal order, we can simply perform a pre-order traversal of the tree and collect all node references into a list. Once we have every node stored in the correct order, we iterate through that list and rewire each node: set its right pointer to the next node in the list and its left pointer to null.

Think of it like dismantling a mobile hanging from a ceiling. You first carefully remove each piece in a specific order (pre-order: parent first, then left branch, then right branch), laying them out in a line on a table. Then you thread a string through each piece from left to right to form a single chain.

Step-by-Step Explanation

Let's trace through with the tree root = [1, 2, 5, 3, 4, null, 6]:

      1
     / \
    2   5
   / \   \
  3   4   6

Phase 1: Pre-order traversal to collect nodes

Step 1: Visit root node 1. Add to order list.

  • order = [1]

Step 2: Go to left child of 1 → visit node 2. Add to order list.

  • order = [1, 2]

Step 3: Go to left child of 2 → visit node 3. Add to order list.

  • order = [1, 2, 3]

Step 4: Node 3 has no children. Backtrack to node 2. Go to right child of 2 → visit node 4.

  • order = [1, 2, 3, 4]

Step 5: Node 4 has no children. Backtrack to node 2, then to node 1. Go to right child of 1 → visit node 5.

  • order = [1, 2, 3, 4, 5]

Step 6: Go to right child of 5 → visit node 6.

  • order = [1, 2, 3, 4, 5, 6]

Phase 2: Reconnect nodes

Step 7: For each consecutive pair in order list, set current.right = next and current.left = null.

  • 1.right = 2, 1.left = null
  • 2.right = 3, 2.left = null
  • 3.right = 4, 3.left = null
  • 4.right = 5, 4.left = null
  • 5.right = 6, 5.left = null

Result: Tree is now flattened: 1 → 2 → 3 → 4 → 5 → 6

Brute Force — Pre-order Collect and Reconnect — Watch how we first traverse the tree in pre-order to collect all nodes, then reconnect them into a right-skewed chain.

Algorithm

  1. Create an empty list called order to store node references
  2. Perform a pre-order traversal of the tree:
    • If the current node is null, return
    • Add the current node to order
    • Recursively traverse the left subtree
    • Recursively traverse the right subtree
  3. Iterate through order from index 0 to length - 2:
    • Set order[i].left = null
    • Set order[i].right = order[i + 1]

Code

class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> order;
        preorder(root, order);
        for (int i = 0; i < (int)order.size() - 1; i++) {
            order[i]->left = nullptr;
            order[i]->right = order[i + 1];
        }
    }

private:
    void preorder(TreeNode* node, vector<TreeNode*>& order) {
        if (!node) return;
        order.push_back(node);
        preorder(node->left, order);
        preorder(node->right, order);
    }
};
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        order = []

        def preorder(node):
            if not node:
                return
            order.append(node)
            preorder(node.left)
            preorder(node.right)

        preorder(root)

        for i in range(len(order) - 1):
            order[i].left = None
            order[i].right = order[i + 1]
class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> order = new ArrayList<>();
        preorder(root, order);
        for (int i = 0; i < order.size() - 1; i++) {
            order.get(i).left = null;
            order.get(i).right = order.get(i + 1);
        }
    }

    private void preorder(TreeNode node, List<TreeNode> order) {
        if (node == null) return;
        order.add(node);
        preorder(node.left, order);
        preorder(node.right, order);
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse every node exactly once during the pre-order traversal, which takes O(n). Then we iterate through the collected list of n nodes to rewire the pointers, which is another O(n) pass. Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

We store all n node references in the order list, which requires O(n) space. Additionally, the recursive pre-order traversal uses O(h) space on the call stack, where h is the height of the tree. In the worst case (a completely skewed tree), h = n, giving O(n) stack space. Combined: O(n).

Why This Approach Is Not Efficient

While the brute force approach runs in O(n) time, its weakness lies in space usage. We allocate an O(n) list to store every node reference, and the recursion itself uses O(h) call stack space (up to O(n) for skewed trees).

For this problem, the follow-up explicitly asks: Can you flatten the tree in-place with O(1) extra space? The brute force answer is clearly no — it needs O(n) auxiliary storage.

The key insight is that we don't need to collect all nodes first and then rewire. If we could process nodes in a clever order, we could rewire pointers as we go without needing to remember every node. Specifically, if we process the tree from the end of the pre-order sequence backward, we can build the flattened list from tail to head using just a single prev pointer.

Better Approach - Recursive with Previous Node Tracking

Intuition

Instead of collecting all nodes and then reconnecting them, what if we could build the flattened list as we traverse, connecting nodes one at a time?

The trick is to process the tree in reverse pre-order: visit the right subtree first, then the left subtree, then the root. This means we encounter nodes in the exact reverse of the desired order (6, 5, 4, 3, 2, 1 instead of 1, 2, 3, 4, 5, 6).

We maintain a prev pointer that always points to the most recently processed node. When we process a node, we set its right pointer to prev (the node that should come after it in the flattened list) and its left pointer to null. Then we update prev to the current node.

Imagine you are building a chain from the last link backward. You start with the tail link (node 6), and each time you pick up a new link, you attach it to the front of what you've built so far. By the time you reach the first link (node 1), the entire chain is complete.

Step-by-Step Explanation

Let's trace through the same tree:

      1
     / \
    2   5
   / \   \
  3   4   6

We process nodes in reverse pre-order (right → left → root):

Step 1: Recurse to the rightmost node: node 6.

  • Set 6.right = null (prev is null — 6 is the tail)
  • Set 6.left = null
  • Update prev = node 6

Step 2: Backtrack to node 5.

  • Set 5.right = node 6 (prev)
  • Set 5.left = null
  • Update prev = node 5
  • Chain so far: 5 → 6

Step 3: Backtrack through 1, then to 2's right child: node 4.

  • Set 4.right = node 5 (prev)
  • Set 4.left = null
  • Update prev = node 4
  • Chain so far: 4 → 5 → 6

Step 4: Backtrack to 2's left child: node 3.

  • Set 3.right = node 4 (prev)
  • Set 3.left = null
  • Update prev = node 3
  • Chain so far: 3 → 4 → 5 → 6

Step 5: Backtrack to node 2.

  • Set 2.right = node 3 (prev)
  • Set 2.left = null
  • Update prev = node 2
  • Chain so far: 2 → 3 → 4 → 5 → 6

Step 6: Backtrack to node 1 (root).

  • Set 1.right = node 2 (prev)
  • Set 1.left = null
  • Update prev = node 1
  • Chain so far: 1 → 2 → 3 → 4 → 5 → 6

Result: Tree is flattened: 1 → 2 → 3 → 4 → 5 → 6

Recursive Reverse Pre-order — Building the Chain Backwards — Watch how we process nodes from the tail of the pre-order sequence backward, attaching each node to the front of the growing chain using a prev pointer.

Algorithm

  1. Initialize a class-level variable prev = null
  2. Define a recursive function flatten(node):
    • If node is null, return
    • Recursively call flatten(node.right) — process right subtree first
    • Recursively call flatten(node.left) — then process left subtree
    • Set node.right = prev — link current node to the previously processed node
    • Set node.left = null — clear the left pointer
    • Update prev = node — current node becomes the new head of the chain built so far
  3. Call flatten(root) to start the process

Code

class Solution {
    TreeNode* prev = nullptr;
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->right);
        flatten(root->left);
        root->right = prev;
        root->left = nullptr;
        prev = root;
    }
};
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        self.prev = None

        def helper(node):
            if not node:
                return
            helper(node.right)
            helper(node.left)
            node.right = self.prev
            node.left = None
            self.prev = node

        helper(root)
class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each of the n nodes exactly once during the reverse pre-order recursion. Each visit performs a constant amount of work (pointer reassignments). Total: O(n).

Space Complexity: O(h), where h is the height of the tree

The recursion uses call stack space proportional to the height of the tree. For a balanced tree, h = O(log n). For a completely skewed tree (worst case), h = O(n). We don't use any explicit auxiliary data structure — just the prev pointer (O(1)) — but the implicit recursion stack is the bottleneck.

Why This Approach Is Not Efficient

The recursive approach eliminates the need for an explicit O(n) list, which is an improvement. However, it still uses O(h) space on the recursion call stack, where h is the tree height. In the worst case — a left-skewed tree with 2000 nodes — this means O(n) stack frames.

The problem's follow-up challenge asks for a solution with O(1) extra space. Recursion inherently prevents us from achieving this because each function call adds a frame to the stack.

To achieve true O(1) space, we need an iterative approach that avoids both explicit storage and recursion. The key idea comes from Morris Traversal: instead of using a stack to remember where to return, we can temporarily modify the tree's pointers to create "threads" that guide us back. For each node with a left child, we find the rightmost node in the left subtree and thread it to the current node's right child — effectively weaving the left subtree into the right-side chain without any extra memory.

Optimal Approach - Morris Traversal (Iterative In-Place)

Intuition

The optimal approach uses an idea inspired by Morris Traversal to flatten the tree with O(1) extra space and no recursion.

The core observation is: in the pre-order traversal, after we finish visiting all nodes in the left subtree, the very next node we visit is the root's right child. This means the rightmost node of the left subtree is the immediate predecessor of the right child in the pre-order sequence.

So for any node that has a left child, we can:

  1. Find the rightmost node of the left subtree (the predecessor)
  2. Attach the current node's right subtree to this predecessor's right pointer — because that's where the right subtree belongs in the pre-order sequence
  3. Move the entire left subtree to become the right child of the current node
  4. Clear the left pointer
  5. Advance to the next node (the new right child)

Think of it like rearranging a deck of cards. Each time you find a card with two branches, you take the right branch, clip it onto the end of the left branch, then straighten everything to the right. You keep walking down the newly straightened path until no more branches remain.

This approach never needs to backtrack because it restructures the tree as it goes, always moving forward through the right pointers.

Step-by-Step Explanation

Let's trace through the same tree:

      1
     / \
    2   5
   / \   \
  3   4   6

Step 1: Start at node 1. It has a left child (node 2).

  • Find the rightmost node of left subtree: go to 2 → go right to 4. Node 4 has no right child, so 4 is the predecessor.

Step 2: Attach node 1's right subtree to the predecessor.

  • Set 4.right = node 5 (the right child of node 1). Now node 4 connects to node 5.

Step 3: Move the left subtree to become the right child.

  • Set 1.right = node 2 (node 1's left child)
  • Set 1.left = null
  • Tree is now:
1
 \
  2
 / \
3   4
     \
      5
       \
        6

Step 4: Move to node 1.right = node 2. It has a left child (node 3).

  • Find rightmost of left subtree: node 3 has no right child, so 3 is the predecessor.

Step 5: Attach node 2's right subtree to the predecessor.

  • Set 3.right = node 4 (right child of node 2).

Step 6: Move the left subtree to become the right child.

  • Set 2.right = node 3
  • Set 2.left = null
  • Tree is now:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Step 7: Move to node 3. No left child → move to node 3.right = node 4.

Step 8: Move to node 4. No left child → move to node 4.right = node 5.

Step 9: Move to node 5. No left child → move to node 5.right = node 6.

Step 10: Move to node 6. No left child → move to node 6.right = null. Done!

Result: Tree is flattened: 1 → 2 → 3 → 4 → 5 → 6, using O(1) extra space.

Morris Traversal — Iterative In-Place Flattening — Watch how we iteratively restructure the tree by finding predecessors and rewiring pointers, always moving forward without recursion or extra storage.

Algorithm

  1. Set cur = root
  2. While cur is not null:
    a. If cur has a left child:
    • Find the rightmost node of cur's left subtree (call it predecessor):
      • Start at cur.left, keep going right until there is no right child
    • Set predecessor.right = cur.right (attach the right subtree to the end of the left subtree)
    • Set cur.right = cur.left (move the left subtree to the right)
    • Set cur.left = null (clear the left pointer)
      b. Move cur = cur.right (advance to the next node)
  3. When cur becomes null, the tree is fully flattened

Code

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode* pred = cur->left;
                while (pred->right) {
                    pred = pred->right;
                }
                pred->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        cur = root
        while cur:
            if cur.left:
                pred = cur.left
                while pred.right:
                    pred = pred.right
                pred.right = cur.right
                cur.right = cur.left
                cur.left = None
            cur = cur.right
class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode pred = cur.left;
                while (pred.right != null) {
                    pred = pred.right;
                }
                pred.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

Although there is a nested loop (the outer while loop and the inner loop to find the predecessor), each edge in the tree is traversed at most twice: once when cur moves along it, and at most once when finding a predecessor. Since a tree with n nodes has n - 1 edges, the total work across all iterations is O(n).

Space Complexity: O(1)

We use only two pointer variables (cur and pred) regardless of the input size. There is no recursion, no stack, and no auxiliary data structure. The tree is modified in-place. This is the optimal space complexity for this problem and satisfies the follow-up challenge.