Flatten Binary Tree

Tags

Flatten Binary Tree

Category

Binary Trees

Difficulty

Hard

Problem Statement

Given a binary tree, flatten it into a doubly linked list in place. The linked list should follow the in-order traversal of the tree. The left pointer of each node should point to the previous node in the list, and the right pointer should point to the next node. The function should return the head (leftmost node) of the resulting linked list.

Intuition

An in-order traversal of a binary tree visits nodes in left-root-right order. To flatten the tree into a doubly linked list following this order, we can recursively flatten the left and right subtrees first, then connect the current node between the end of the left list and the beginning of the right list. This is a divide-and-conquer approach that works bottom-up.

Approach

  1. Define a recursive helper that returns both the head and tail of the flattened linked list for a given subtree.
  2. Base case: if the node is null, return (null, null).
  3. Recursively flatten the left subtree, obtaining leftHead and leftTail.
  4. Recursively flatten the right subtree, obtaining rightHead and rightTail.
  5. Connect leftTail.right to the current node, and currentNode.left to leftTail (if left subtree exists).
  6. Connect currentNode.right to rightHead, and rightHead.left to the current node (if right subtree exists).
  7. The head of the combined list is leftHead (or the current node if no left subtree).
  8. The tail of the combined list is rightTail (or the current node if no right subtree).
  9. Return the head and tail.

Pseudocode

function flattenBinaryTree(root):
    head, _ = flattenTree(root)
    return head

function flattenTree(node):
    if node is null:
        return (null, null)

    leftHead, leftTail = flattenTree(node.left)
    rightHead, rightTail = flattenTree(node.right)

    if leftTail is not null:
        leftTail.right = node
        node.left = leftTail

    if rightHead is not null:
        node.right = rightHead
        rightHead.left = node

    overallHead = leftHead if leftHead is not null else node
    overallTail = rightTail if rightTail is not null else node

    return (overallHead, overallTail)

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Each node is visited exactly once.
  • Space: O(h) where h is the height of the tree, due to the recursion stack. O(log n) for balanced trees, O(n) for skewed trees.

Key Insights

  • Returning both head and tail from recursion avoids the need to traverse lists to find endpoints, keeping the algorithm O(n).
  • The tree is modified in place — no new nodes are created.
  • In-order traversal order is maintained because we connect: left subtree list -> current node -> right subtree list.
  • This is a clean example of divide-and-conquer on trees.
  • An alternative iterative approach can use a stack-based in-order traversal and link nodes as they are visited.

Edge Cases

  • The tree is empty (null root) — return null.
  • The tree has only one node — return that node with both left and right set to null.
  • A completely left-skewed tree — already almost a linked list going left; needs pointer rewiring.
  • A completely right-skewed tree — similar but in the other direction.
  • The tree has only left children or only right children — the result is identical to the original structure with minor pointer adjustments.

Linked mentions