A design tool stores a widget tree: each node is a panel, with a left child and a right child. Product wants a linear inspector — same panels, preorder, each pointing only at the next — so a reviewer can step through without a stack of open branches. The intern version walked the tree, copied values into an ArrayList, and built a new chain. The order was preorder. The nodes were not. Every click handler that still held a TreeNode from the original tree never saw the spine.

Flattening means each node’s right becomes the next preorder node and left is null — the same TreeNode objects, not a ListNode chain. The binary tree post owns shape and traversals. Reverse Linked List is the same idea — same nodes, new links — on next, not right. Invert Binary Tree also rewires children in place; that mutation is a left/right swap, not a spine. Here we only hang a preorder chain on the nodes you were given.

The problem

Given the root of a binary tree, flatten it in place so a preorder walk of the original tree is now a right spine: every left is null, and right is the next preorder node. Return nothing; mutate the tree. An empty tree and a single node are already flat.

      1
     / \
    2   5
   / \
  3   4

1 → 2 → 3 → 4 → 5

A node is the usual three fields. After flatten it still is — you do not switch types.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Note: In-place means the same node objects, new child links. Copying values into a list and building a fresh chain passes a value-order test and fails any test that identity of nodes matters — or any caller that still holds the original root and expects its children to have moved. Reverse Linked List named that trap on ListNode. Do not start allocating ListNode here.

A copied chain is the honest brute force

Walk preorder, stash the values, then hang a new TreeNode for each. Correct order. A second tree — except you kept root so the void signature still compiles.

void flattenCopy(TreeNode root) {
    if (root == null) {
        return;
    }
    List<Integer> vals = new ArrayList<>();
    preorder(root, vals);
    TreeNode cur = root;
    for (int i = 1; i < vals.size(); i++) {
        cur.left = null;
        cur.right = new TreeNode(vals.get(i));
        cur = cur.right;
    }
    cur.left = null;
    cur.right = null;
}

void preorder(TreeNode node, List<Integer> vals) {
    if (node == null) {
        return;
    }
    vals.add(node.val);
    preorder(node.left, vals);
    preorder(node.right, vals);
}

Callers that held node 2 still see 3 and 4 as children. You paid O(n) extra nodes for a question that only asked you to rewire pointers. Collecting the original nodes into a list and then pointing each right at the next keeps identity and is still O(n) extra.

Reverse post-order: hang the spine from the tail

Visit right, then left, then the node. Keep a prev that is the head of the spine already built — the next preorder node after this one, because you already flattened everything that should follow. Attach node.right = prev, clear left, then prev = node. The last preorder node is visited first and becomes the tail.

flatten(1)                    prev = null
  flatten(5)                  right first
    5.right = null, left = null, prev = 5
  flatten(2)
    flatten(4)
      4.right = 5, left = null, prev = 4
    flatten(3)
      3.right = 4, left = null, prev = 3
    2.right = 3, left = null, prev = 2
  1.right = 2, left = null, prev = 1

1 → 2 → 3 → 4 → 5

The Java is that rewind. prev is a one-slot holder so each return sees the spine already hung, and a second call does not inherit the last node of the previous tree. Java has no pass-by-ref TreeNode.

void flatten(TreeNode root) {
    flatten(root, new TreeNode[] {null});
}

void flatten(TreeNode node, TreeNode[] prev) {
    if (node == null) {
        return;
    }
    flatten(node.right, prev);
    flatten(node.left, prev);
    node.right = prev[0];
    node.left = null;
    prev[0] = node;
}

Time is O(n) — each node is visited once. Extra heap is O(1) besides the call stack. The stack is still O(h); a left spine of a million nodes is a million frames. That bound is the recursive bill, not Morris.

Do not flatten left, hang it on right, and walk the new spine to reattach the original right without saying the cost. Finding that tail at every node is O(n²) on a left spine. Reverse post-order never searches for a tail: prev already is one.

Empty tree: the helper sees null and returns. One node: both recursive calls return, you set right to null (the starting prev), left to null, and stop. Already a spine. No extra branch.

What interviewers usually poke next

  • Morris. If node has a left child, find the rightmost node of that left subtree, hang the original right there, move left onto right, null left. Same preorder spine. O(1) extra including the stack. Mention it; write it if they ask for true constant space.
  • Explicit stack preorder. Push right, then left, rewire as you pop. Same O(h) extra, no JVM stack. ArrayDeque, not java.util.Stack. Write it if they ban recursion.
  • Invert Binary Tree. Also mutates children. Swap is not flatten. Do not start inverting inside flatten.
  • Leave the original intact. Then the copied chain is the spec, and you should say so before you allocate.

You are done with this problem when you can flatten 1 / 2, 5 with 2 / 3, 4 on a whiteboard into 1 → 2 → 3 → 4 → 5 without allocating a ListNode, and you can name the empty-tree and single-node cases without a special branch.