226 · Invert Binary Tree

The whole of sub-variant J in three lines: recurse, then rewire. The trap is not the swap — it is writing the swap as two assignments that read each other, so the second one sees a pointer the first already overwrote.

1 — The problem

Mirror the tree: every node's left and right children exchange places, recursively. Sub-variant J is the family where the recursion rewires pointers rather than computing a value, and this is its simplest member — the return value carries no information at all.

That difference matters for one reason: once you are mutating, the order of operations becomes load-bearing. A value-returning recursion can compute its children in any order; a rewiring one usually cannot.

2 — Recurse, then rewire

Watch the subtrees get inverted from the bottom up, and each node's swap happen only after both of its children are already mirrored.

Capturing both children into locals before assigning either is what makes lines 5–6 safe. They read L and R, not nd.left and nd.right, so neither assignment can disturb the other.

2.1 The self-destroying swap

This is the version that gets written under time pressure, and it is wrong:

TreeNode invert(TreeNode nd) {          // ✗
    if (nd == null) return null;
    nd.left  = invert(nd.right);
    nd.right = invert(nd.left);         // nd.left is the NEW left — the old right
    return nd;
}

Line 3 replaces nd.left with the inverted right subtree. Line 4 then reads nd.left — which is now that same subtree — and inverts it a second time, putting it back the way it started, on both sides. The original left subtree is dropped entirely. The output is a tree in which the old right subtree appears twice, once mirrored and once not.

The fix is either the local variables above, or a classic three-line swap done before recursing:

TreeNode invert(TreeNode nd) {
    if (nd == null) return null;
    TreeNode t = nd.left; nd.left = nd.right; nd.right = t;
    invert(nd.left);
    invert(nd.right);
    return nd;
}

Both work, because inverting is independent per node — no node's swap depends on whether its children have been swapped yet. That independence is special to this problem. In LC 114 the parent's rewiring genuinely needs the children already flattened, and the order stops being negotiable.

2.2 Iteratively

Any traversal works, since the swaps are independent — visit every node once and swap:

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode nd = q.poll();
        TreeNode t = nd.left; nd.left = nd.right; nd.right = t;
        if (nd.left  != null) q.add(nd.left);
        if (nd.right != null) q.add(nd.right);
    }
    return root;
}

3 — Complexity and edge cases

• Time O(n), space O(h) recursive or O(width) iterative.
• Empty tree: returns null. The guard covers it.
• Single node: unchanged — two nulls swap to two nulls.
• Node with one child: the child moves to the other side, and a null moves in behind it. No special case needed; that is what makes the null-based guard right here.
• The tree is mutated in place. The return value is a convenience, not a new tree. If the caller holds another reference to the original, it now sees the inverted version.
• Common bug: the self-destroying swap above.
• Common bug: returning nd.left or building a new node instead of returning nd. The problem asks for the same tree, rearranged.

4 — Reference implementation

public TreeNode invertTree(TreeNode nd) {
    if (nd == null) return null;
    TreeNode L = invertTree(nd.left);    // capture both BEFORE assigning either
    TreeNode R = invertTree(nd.right);
    nd.left  = R;
    nd.right = L;
    return nd;
}