Flatten Binary Tree to Linked List

Description

Flattening turns a binary tree into a linked list without creating a single new node. Each node's right pointer becomes "next", and its left pointer is either cleared or reused as "previous". Interviews ask for two versions: a singly linked list in preorder, and a doubly linked list in inorder. The tricky part is order. A node can only point at the rest of the list once that rest exists.

We'll go from simple to more technical:

1. The pattern: build the preorder list backwards, from its last node to its first.
2. A second flavor: a doubly linked list in inorder.
3. Where in-place flattening helps.
4. The bugs: building in the wrong order and leaving old left pointers behind.

The approach

In the finished list, every node points at the node after it in preorder. The easy way to get that right is to build the list from its end. Visit the nodes in the exact reverse of preorder: right subtree, then left subtree, then the node itself. Keep prev, the first node of the part you've already built. Each node sets right = prev, clears left, and becomes the new prev.

Take this tree. Its preorder is 8, 3, 1, 6, 10, 9, 14.

The walk links the nodes in reverse preorder. Each one goes in front of the chain built so far:

TreeNode prev = null;

void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.right);   // flatten right first...
    flatten(root.left);    // ...then left...
    root.right = prev;     // ...so `prev` is always the correctly-flattened chain so far
    root.left = null;
    prev = root;
}

class Solution:
    def __init__(self):
        self.prev = None

    def flatten(self, root: TreeNode | None) -> None:
        if root is None:
            return
        self.flatten(root.right)   # flatten right first...
        self.flatten(root.left)    # ...then left...
        root.right = self.prev     # ...so self.prev is always the correctly-flattened chain so far
        root.left = None
        self.prev = root

The first node to be linked is the last one in preorder (14). Its prev is still null, which is right: nothing comes after it. Every later node plugs itself in front. When the recursion gets back to the root, the whole list reads in preorder.

A second flavor: a doubly linked list in inorder

Now the list should follow inorder (1, 3, 6, 8, 9, 10, 14 for the tree above), with links both ways. right means "next" and left means "previous". This time the list is built from the front. Walk in ordinary inorder: left subtree, node, right subtree. prev is the node you visited just before this one. Link the two in both directions and move on. The first node you visit has no prev, so it becomes the head.

TreeNode prev = null, head = null;

void convert(TreeNode node) {
    if (node == null) return;
    convert(node.left);
    if (prev == null) {
        head = node;          // the first node visited in inorder becomes the list's head
    } else {
        prev.right = node;    // link the previous node's "next" forward to this one
        node.left = prev;     // link this node's "previous" backward to the previous one
    }
    prev = node;
    convert(node.right);
}

def tree_to_doubly_list(root: TreeNode | None) -> TreeNode | None:
    prev = head = None

    def convert(node: TreeNode | None) -> None:
        nonlocal prev, head
        if node is None:
            return
        convert(node.left)
        if prev is None:
            head = node           # the first node visited in inorder becomes the list's head
        else:
            prev.right = node     # link the previous node's "next" forward to this one
            node.left = prev      # link this node's "previous" backward to the previous one
        prev = node
        convert(node.right)

    convert(root)
    return head

Changing a node's left here is safe. By the time the walk reaches a node, its left subtree is already finished.

Where you'll see it

Flattening helps when you need a tree as a sequence and don't want to copy it. A classic use is merging two binary search trees. Flatten each one into a sorted list, merge the lists, then build a balanced tree from the result.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Preorder visits left before right. So why does the flatten walk do the right subtree first?

2. After root.right = prev, why set root.left to null too?

3. Why does the doubly linked version use plain inorder, while flatten uses the reverse order?

Key takeaways

• Flatten to preorder by visiting right, left, then the node, and linking each node in front of prev.
• After setting right, clear left, or the list keeps a stale pointer.
• The doubly linked version walks in plain inorder and links each node to the one before it, both ways.
• Both reuse the tree's own pointers and create no new nodes.