Flatten Binary Tree to Linked List – Solution & Complexity

Q: What is the time and space complexity of Flatten Binary Tree to Linked List?

The optimal Flatten Binary Tree to Linked List solution runs in `O(n)` time and `O(h)` space. Postorder-style DFS flattens left and right subtrees, then splices the flattened left chain between the current node and the flattened right chain in preorder order.

Q: What is the most efficient way to solve Flatten Binary Tree to Linked List?

Postorder-style DFS flattens left and right subtrees, then splices the flattened left chain between the current node and the flattened right chain in preorder order. This gives `O(n)` time complexity, and is a classic binary tree, depth first search, linked list, and recursion problem.

Q: How do you solve Flatten Binary Tree to Linked List in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Flatten Binary Tree to Linked List solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Flatten Binary Tree to Linked List an easy or hard interview question?

Flatten Binary Tree to Linked List is generally rated **Medium**. It tests binary tree, depth first search, linked list, and recursion, which are common coding-interview patterns.

Solution Walkthrough

1. Understand what the flattened tree should look like

The final structure must follow preorder traversal: visit the current node, then its left subtree, then its right subtree.
Every node's left pointer must become null.
Every node's right pointer should point to the next node in preorder order, so the tree becomes a single right-leaning chain.

2. Start with a simple preorder list approach

Run a preorder traversal and store every visited node in an array.
Then walk that array and relink each node so left = null and right = next node.
This is easy to reason about and correct, but it uses O(n) extra space for the stored traversal.

def flatten(root: TreeNode) -> TreeNode:
    nodes = []

    def preorder(node: TreeNode | None) -> None:
        if node is None:
            return
        nodes.append(node)
        preorder(node.left)
        preorder(node.right)

    preorder(root)

    for i in range(len(nodes) - 1):
        nodes[i].left = None
        nodes[i].right = nodes[i + 1]

    if nodes:
        nodes[-1].left = None
        nodes[-1].right = None
        return nodes[0]

    return None

3. Improve it by splicing subtrees in place

A more space-efficient idea is to flatten the left and right subtrees first.
Once both sides are already flattened, place the flattened left subtree between the current node and the flattened right subtree.
In other words: save the original right subtree, move the left subtree to the right, null out left, then connect the left subtree's tail to the saved right subtree.

4. Optimal recursive in-place solution

Let a helper return the tail node of the flattened subtree rooted at the current node.
Recursively flatten the left and right subtrees first.
If a left subtree exists, splice it between the node and the original right subtree, then return the rightmost tail that now ends the flattened subtree.

def flatten(root: TreeNode) -> TreeNode:
    def helper(node: TreeNode | None) -> TreeNode | None:
        if node is None:
            return None

        left_tail = helper(node.left)
        right_tail = helper(node.right)

        if node.left is not None:
            saved_right = node.right
            node.right = node.left
            node.left = None
            left_tail.right = saved_right

        return right_tail or left_tail or node

    helper(root)
    return root

5. Dry run on the classic example

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

Flatten subtree rooted at 2. Its preorder is 2,3,4, so that subtree becomes 2 -> 3 -> 4.
Flatten subtree rooted at 5. Its preorder is 5,6, so it becomes 5 -> 6.
Return to 1. Save the original right subtree head 5.
Move the flattened left subtree to 1.right, so now 1 -> 2 -> 3 -> 4.
Connect the tail of that moved left chain (node 4) to the saved right subtree head 5.
Final chain: 1 -> 2 -> 3 -> 4 -> 5 -> 6, serialized as [1,null,2,null,3,null,4,null,5,null,6].

6. Common mistakes

Forgetting to save the original right subtree before overwriting node.right.
Forgetting to set node.left = null, which leaves stray left pointers and breaks the required output shape.
Returning None/null/void instead of returning the mutated root.
Re-linking the current node before recursively flattening its children, which can lose part of the tree.

7. Edge cases to test mentally

Empty tree: input [] should return [].
Single node: input [1] stays [1].
Already-flat right chain: the algorithm should preserve it.
Left-only chain: every node shifts from left pointers to right pointers in the same preorder order.

8. Final full solution and complexity

Flatten each subtree with a postorder-style recursion that returns the tail of the flattened result. Each node is visited once, so time is O(n). The extra space is O(h) for the recursion stack, where h is the tree height.

def flatten(root: TreeNode) -> TreeNode:
    def helper(node: TreeNode | None) -> TreeNode | None:
        if node is None:
            return None

        left_tail = helper(node.left)
        right_tail = helper(node.right)

        if node.left is not None:
            saved_right = node.right
            node.right = node.left
            node.left = None
            left_tail.right = saved_right

        return right_tail or left_tail or node

    helper(root)
    return root

Flatten Binary Tree to Linked List – Solution & Complexity

Solution Walkthrough

1. Understand what the flattened tree should look like

2. Start with a simple preorder list approach

3. Improve it by splicing subtrees in place

4. Optimal recursive in-place solution

5. Dry run on the classic example

6. Common mistakes

7. Edge cases to test mentally

8. Final full solution and complexity

FAQ

What is the time and space complexity of Flatten Binary Tree to Linked List?

What is the most efficient way to solve Flatten Binary Tree to Linked List?

How do you solve Flatten Binary Tree to Linked List in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Flatten Binary Tree to Linked List an easy or hard interview question?

See also