{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Flatten Binary Tree to Linked List – Solution & Complexity

Interview solutions
/
Flatten Binary Tree to Linked List

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 5: Dry run on the classic example

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

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

  6. Step 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. Step 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. Step 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

FAQ

See also

Practice Flatten Binary Tree to Linked List online (run code in the browser)Balanced Binary Tree solution (easy)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)Binary Tree Preorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?