Topics › Binary Trees › Hard Problems

Flatten Binary Tree to Linked List

Medium TUF ID 486 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given the root of a binary tree, flatten it in place into a “linked list” made of the same nodes:

• the right pointer of each node points to the next node of the list, and the last node’s right is null;
• every left pointer is null;
• the list visits the nodes in preorder (node, left subtree, right subtree).

The method returns nothing; the tree itself is rewired. Constraints (LeetCode version): up to 2000 nodes, values in [-100, 100]. Follow-up: can you do it with O(1) extra space?

Example 1

        1
       / \
      2   5
     / \   \
    3   4   6

becomes  1 -> 2 -> 3 -> 4 -> 5 -> 6     // the preorder of the tree, linked through right pointers

Example 2

root = []      -> []         // nothing to do
root = [0]     -> [0]        // a single node is already a list

Approach 1: Brute force, store the preorder first

Intuition. The required order is simply preorder. Record the nodes in preorder in a list first, while the tree is still intact, and only then rewire: node i gets left = null and right = node i + 1. Collecting before modifying is what keeps this safe; changing pointers during the traversal would destroy the parts of the tree that have not been visited yet.

Algorithm.

1. Traverse the tree in preorder and append every node to a list.
2. For each index i, set order[i].left = null and order[i].right = order[i + 1] (or null for the last node).

static void bruteForce(TreeNode root) {
    List<TreeNode> order = new ArrayList<>();
    collectPreorder(root, order);
    for (int i = 0; i < order.size(); i++) {
        TreeNode node = order.get(i);
        node.left = null;
        node.right = i + 1 < order.size() ? order.get(i + 1) : null;
    }
}

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

Complexity. Time O(n): one traversal and one pass over the list. Space O(n) for the list, plus O(h) recursion depth.

Approach 2: Better, build the list from its tail

Intuition. In the finished list, a node is followed by its flattened left subtree, then its flattened right subtree, then whatever comes after the node’s whole subtree (call that the tail). It is hard to build that from the front, because when we are at a node we do not yet know where its left subtree’s list will end. It is easy from the back: if we already have the tail, then

1. flatten the right subtree and hang tail after it; its head becomes the new tail,
2. flatten the left subtree and hang that after it; its head becomes the new tail,
3. point the node at the result and clear its left pointer.

That is a traversal in reverse preorder (right, left, node), each step prepending one node to a list that grows backwards. The common version of this solution keeps the tail in a global prev variable; here it is passed in as a parameter and returned, which is the same idea without shared state.

Algorithm.

1. flattenOnto(node, tail): if node is null, return tail.
2. tail = flattenOnto(node.right, tail), then tail = flattenOnto(node.left, tail).
3. node.right = tail, node.left = null, return node.

Note the order: node.right and node.left are read (by the recursive calls) before the node itself is modified, and the recursive calls only touch nodes inside those subtrees.

static void better(TreeNode root) {
    flattenOnto(root, null);
}

// flattens the subtree at node, appends tail after it, and returns the head of the result
static TreeNode flattenOnto(TreeNode node, TreeNode tail) {
    if (node == null) return tail;
    tail = flattenOnto(node.right, tail);                   // right subtree comes last in preorder, so do it first
    tail = flattenOnto(node.left, tail);
    node.right = tail;
    node.left = null;
    return node;
}

Dry run on Example 1 (calls finish in the order right subtree first):

Complexity. Time O(n): each node is handled once. Space O(h) for the recursion, which is O(n) for a skewed tree but no longer needs a separate list.

Approach 3: Optimal, Morris-style rewiring

Intuition. Look at one node cur that has a left child. In preorder, cur is followed by its left subtree, and the left subtree is followed by cur’s right subtree. The last node of the left subtree in preorder is its rightmost node pred (start at cur.left, keep going right), and pred.right is null. So one local rewiring puts the three pieces in the right order:

1. pred.right = cur.right: the right subtree now hangs after the left subtree’s last node.
2. cur.right = cur.left, cur.left = null: the left subtree moves to the right side.

The rest of the tree has not been flattened yet, but the preorder of the whole tree is unchanged by this move, and cur now has no left child. Step to cur.right and repeat. When cur falls off the end, no node has a left child, and since preorder was preserved at every step, the right chain is exactly the original preorder.

This is the same “rightmost node of the left subtree” trick that Morris traversal uses, except that here the pointer is rewired permanently instead of being a temporary thread.

Algorithm.

1. cur = root. While cur != null:
2. If cur.left != null: find pred, the rightmost node of cur.left; set pred.right = cur.right, cur.right = cur.left, cur.left = null.
3. cur = cur.right.

static void optimal(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left != null) {
            TreeNode pred = cur.left;
            while (pred.right != null) pred = pred.right;   // last node of the left subtree in preorder
            pred.right = cur.right;                         // the right subtree follows it
            cur.right = cur.left;                           // the left subtree moves to the right
            cur.left = null;
        }
        cur = cur.right;
    }
}

Dry run on Example 1:

Complexity. Time O(n). Each node becomes cur once. The search for pred walks nodes of cur’s left subtree; immediately afterwards those nodes are on the main right chain, and nodes on that chain are never put back into a left subtree, so every node is walked by a pred search at most once. Space O(1): two pointers.

Edge cases and pitfalls

• Empty tree and single node. All three methods do nothing; the result is already a valid list.
• Forgetting to clear left. The output must have every left pointer set to null. A list whose nodes still point left is wrong even if the right chain is correct, and the tests check both conditions.
• Losing the right subtree. In the optimal approach, cur.right must be saved (attached to pred) before it is overwritten with cur.left. Doing the two assignments in the other order drops the right subtree.
• Modifying while traversing. A naive recursive preorder that rewires as it goes reads node.right after it has already been overwritten. Approach 1 collects first; Approach 2 reads both children before modifying the node.
• Recursion depth. Approaches 1 and 2 recurse h levels deep, up to n for a chain. Approach 3 is iterative and safe for any shape.

The tests cover the example, a tree with two levels of nesting, a single node, an empty tree, a left chain, a tree that is already flat, a zig-zag, and a 50000-node balanced tree.

Related problems

• Morris Preorder Traversal of a Binary Tree uses the same rightmost-node pointer, but only temporarily.
• Preorder Traversal defines the order the flattened list must follow.
• Binary Tree to Doubly Linked List is a close cousin that links nodes in inorder and uses both pointers.