114 · Flatten Binary Tree to Linked List

Two solutions worth knowing: reverse-postorder with a prev pointer, and the O(1)-space Morris-style rewiring. The second is the follow-up they actually want.

1 — The problem

Flatten the tree in place into a "linked list" that uses the right pointers, with every left set to null, and the order must be the tree's preorder.

The naive approach — collect the preorder into a list, then relink — is O(n) time and O(n) space and gets you nowhere near the follow-up. The interesting question is how to rewire without a buffer.

The obstacle is specific: at node nd you want nd.right = nd.left, but that overwrites the pointer to the right subtree, which still has to be attached after the left subtree's last node. So you need to know where the left subtree ends — and that is the whole problem. Two answers:

2 — Building the list backwards

The recursion visits right, then left, then the node — the exact reverse of preorder. So the nodes get rewired in the order 6, 5, 4, 3, 2, 1, and each one simply points at whatever was handled immediately before it.

Because both subtrees are fully processed before line 6 runs, nd's children have already been consumed into the growing list and the pointers are free to overwrite. Reverse the two recursive calls and it breaks immediately — the left subtree gets appended before the right, so the order comes out wrong.

This is the same trick as reversing a linked list by building the answer from the tail, and the same trick LC 106 uses to consume postorder backwards: when attaching to the end is awkward, build in the opposite direction and attach to the front.

2.1 The O(1)-space version

The follow-up asks for constant extra space, which rules out the recursion stack. The Morris-style loop finds the splice point explicitly:

public void flatten(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left != null) {
            TreeNode pred = cur.left;
            while (pred.right != null) pred = pred.right;  // rightmost of the left subtree
            pred.right = cur.right;      // hang the right subtree off it
            cur.right  = cur.left;       // left subtree becomes the right chain
            cur.left   = null;
        }
        cur = cur.right;                 // walk into the part just spliced
    }
}

Why pred is the right splice point: in preorder, the node immediately before the right subtree is the last node of the left subtree, and the last node of a preorder walk of any subtree is its rightmost descendant. So pred.right is precisely the slot the right subtree belongs in.

The inner while makes this look quadratic. It is not: each edge of the tree is traversed at most twice over the whole run — once by the outer walk, once by an inner search — so the total is O(n).

2.2 Which to write

3 — Complexity and edge cases

• Recursive: O(n) time, O(h) space. Morris: O(n) time, O(1) space.
• Empty tree: nothing happens; both versions guard.
• Single node: already flat — right becomes null via prev, left was already null.
• Already a right chain: Morris skips every node (no left children) and does one pass. The recursion still walks it, using O(n) stack.
• Left-only chain is the worst case for the recursion's depth and the case where Morris does the most splicing.
• Common bug: forgetting nd.left = null. The list looks right if you only follow right pointers, and the judge fails you on the stale left pointers.
• Common bug: recursing left before right in the recursive version. Produces a plausible but wrongly-ordered chain.
• Common bug: making prev a parameter instead of shared state — the same error as LC 297's cursor.

4 — Reference implementation

private TreeNode prev = null;

public void flatten(TreeNode nd) {
    if (nd == null) return;
    flatten(nd.right);        // RIGHT first — we are building backwards
    flatten(nd.left);
    nd.right = prev;          // attach to what was handled last
    nd.left  = null;
    prev = nd;
}