A design tool stores a widget tree: each node is a panel, with a left child and a right child. Product wants an RTL preview — flip the layout in place. The intern version walked the tree, allocated a new node per widget, and hung the inverted children on the copies. The preview looked mirrored. Every click handler still bound to the original nodes never saw the flip.

Inverting a binary tree means swapping left and right at every node of the tree you were given. The binary tree post owns shape and traversals. Here we only care about exchanging the two child pointers, then doing the same work in both subtrees.

The problem

Given the root of a binary tree, invert it so every node’s left and right children are exchanged, and return the root. An empty tree and a single node are legal; both are already inverted.

      4                 4
     / \               / \
    2   7     →       7   2
   / \ / \           / \ / \
  1  3 6  9         9  6 3  1

A node is the usual three fields:

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

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

Note: In-place means the same node objects, swapped child links. Copying values into a new tree passes a value-shape 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.

A copied tree is the honest brute force

Build a new node for each original, attach the inverted right as the new left, and the inverted left as the new right. Correct. A second tree.

TreeNode invertCopy(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode copy = new TreeNode(root.val);
    copy.left = invertCopy(root.right);
    copy.right = invertCopy(root.left);
    return copy;
}

The original tree is untouched. Callers that held root still see 2 on the left of 4. You paid O(n) extra nodes for a question that only asked you to swap pointers.

Swap left and right, then return the same root

Invert both subtrees, then exchange the two child pointers on this node. Recursing first or swapping first and then recursing on the new children both work. Overwriting left before you have saved it does not.

invert(4)
  invert(2)
    invert(1)  leaf, swap null/null
    invert(3)  leaf, swap null/null
    2.left = 3, 2.right = 1
  invert(7)
    invert(6)  leaf
    invert(9)  leaf
    7.left = 9, 7.right = 6
  4.left = 7, 4.right = 2

The Java is that walk. The two recursive results are the inverted subtrees; assigning them crossed is the swap.

TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

Time is O(n) — each node is visited once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit stack is the same bound without blowing the JVM stack.

Do not write root.left = invertTree(root.right) and then invert root.left into root.right. The original left subtree is gone, and the original right is inverted twice. Save both results (or swap via a temporary), then assign.

Empty tree: root is null, return null. One node: both recursive calls return null, you swap null with null, return that node. No extra branch.

What interviewers usually poke next

  • Iterative BFS or an explicit stack. Same swap, no recursion. Queue the node, exchange its children, offer the non-null ones. Mention it; write it if they ask.
  • Symmetric tree. Ask whether a tree is a mirror of itself. Related idea, different contract: compare, do not mutate.
  • Flatten to a linked list. Rewire children into a spine. Also mutation, not a mirror. Do not start flattening inside invertTree.
  • Leave the original intact. Then the copied tree is the spec, and you should say so before you allocate.

You are done with this problem when you can invert 4 / 2, 7 on a whiteboard without losing a child pointer, and you can name the empty-tree and single-node returns without a special case.