LeetCode 114 – Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List has a natural answer that allocates, a better answer that does not, and a third that uses no extra space at all and is genuinely elegant. It is the best problem on the list for the idea that pointer surgery can replace a data structure, and the O(1) solution is the same threading trick as Morris traversal from problem 94.

The problem

Flatten the tree into a "linked list" in place: every node's right points to the next node in preorder, and every left is null. The result is still a TreeNode chain, not a new type.

      1
     / \
    2   5        ->   1 -> 2 -> 3 -> 4 -> 5 -> 6
   / \   \            (all via .right, every .left null)
  3   4   6

  []   -> []
  [0]  -> [0]

Preorder is the required order, which is worth confirming against the example rather than assuming — 1, 2, 3, 4, 5, 6 is root, left subtree, right subtree, applied recursively.

Why the naive recursion breaks

"Do a preorder traversal and rewire as you go" fails immediately:

at node 1:  right = left
            1 -> 2 ...   and the subtree rooted at 5 is now unreachable

Overwriting right destroys the pointer to a subtree you have not visited. The recursion needs the old value after it has been overwritten, which is the tell that something has to be saved first.

The two-pass version — collect the preorder into a list, then rewire — sidesteps this and is a perfectly acceptable first answer. It costs O(n) space. Say it, then improve it.

The reverse-preorder trick

Traverse in reverse preorder — right subtree, then left subtree, then the node — keeping a pointer to the previously visited node. Because you build the list back to front, the node you attach to is always one you have already finished with, so nothing is destroyed:

visit order: 6, 5, 4, 3, 2, 1
at each node:  node.right = previous;  node.left = null;  previous = node

This is the same idea as writing backwards in Merge Sorted Array: when the write would clobber something unread, go the other way. It is O(h) stack rather than O(n), and it is a good answer.

The O(1) version

Better still, and no recursion. For each node that has a left subtree, the last node of that left subtree in preorder — its rightmost descendant — is exactly the node that must precede the right subtree. So splice the right subtree onto it, move the left subtree across, and walk on:

      1                 1                    1
     / \                 \                    \
    2   5      ->         2          ->        2
   / \   \               / \                    \
  3   4   6             3   4                    3
                             \                    \
                              5                    4
                               \                    \
                                6                    5 -> 6

find 4 (rightmost of 1's left subtree), hang 5 there,
then move the whole left subtree to the right and null out left.

Java

class Solution {
    public void flatten(TreeNode root) {
        TreeNode current = root;

        while (current != null) {
            if (current.left != null) {
                // The last node of the left subtree in preorder is its rightmost
                // descendant -- that is where the right subtree belongs.
                TreeNode predecessor = current.left;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = current.right;

                current.right = current.left;
                current.left = null;
            }

            current = current.right;    // walk into the list we are building
        }
    }
}

It looks quadratic and is not. Each edge of the original tree is traversed at most twice — once while walking down the main chain, once while searching for a predecessor — so the whole thing is O(n). That amortised argument is the same one that makes Morris traversal linear, and being able to give it is most of the value of knowing this solution.

The method returns void and mutates. Reassigning root inside would change nothing for the caller — Java passes the reference by value — which is why the loop uses a separate current.

Python

class Solution:
    def flatten(self, root: TreeNode) -> None:
        current = root

        while current:
            if current.left:
                predecessor = current.left
                while predecessor.right:
                    predecessor = predecessor.right

                predecessor.right = current.right
                current.right = current.left
                current.left = None

            current = current.right

Six lines of pointer work and no auxiliary structure at all. The order of the three assignments matters: predecessor.right must be set before current.right is overwritten, or the right subtree is lost — the same clobbering the naive recursion hit, avoided by sequencing rather than by saving.

Complexity

All three are linear in time; the whole exercise is about the space column. Give the first, then improve — arriving at O(1) after two stated alternatives reads far better than producing it cold, and if the interviewer asks why it is not O(n²) you need the amortised argument ready anyway.

The pattern

Splicing a subtree onto the rightmost node of another is exactly Morris traversal's threading step, seen in problem 94 — the difference is that Morris removes its threads afterwards and this problem keeps them, because the threads are the answer.

More broadly: whenever a transformation would overwrite something still needed, the options are save it, reorder the writes, or traverse in the opposite direction. This problem has one solution of each kind, which is why it is worth doing all three.

What the interviewer is checking

• That you notice the naive rewiring destroys the right subtree.
• That the order is preorder, confirmed against the example.
• That every left is nulled, not just rewired.
• That you offer O(n) space first and then improve it.
• The amortised argument for why predecessor-searching is not O(n²).
• Empty tree, single node, and a tree that is already a right chain.
• That the assignments are sequenced so nothing is lost.