Invert Binary Tree

1. Problem & Core Objective

Given the root of a binary tree, invert it — mirror it left-to-right — and return the root.

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

Constraints: 0 <= nodes <= 100 · -100 <= Node.val <= 100

What's actually being tested: whether you can write a tree recursion at all. This is the "hello world" of tree problems — the entire body is a swap. It's here to establish the recursive shape that the other fourteen questions build on.

2. First-Principles Thought Process

What inverting means

Mirroring a tree means: at every node, the left subtree and the right subtree trade places. Not just at the root — at every node, all the way down.

The recursive contract

Tree recursion is easiest when you state a contract and trust it:

invert(node) mirrors the subtree rooted at node and returns it.

Assume that's true for the children. Then mirroring node is:

1. Mirror the left subtree (trust the contract).
2. Mirror the right subtree (trust the contract).
3. Swap the two child pointers.

That's it. The recursion handles the descent; the body is one swap.

Why the order doesn't matter here

You can swap first and then recurse, or recurse first and then swap — both work. That's unusual, and worth noticing: it's true because the swap at a node is independent of what happens inside its subtrees. Swapping doesn't change the contents of either subtree, only which slot it occupies.

Most tree problems are not like this. In Diameter and Max Path Sum the parent genuinely needs its children's results, so the recursion must complete before the body runs. Recognising which kind you have is the actual skill.

The base case

null is an empty tree, and the mirror of an empty tree is an empty tree. So if (root == null) return null; — no special handling for leaves, since a leaf's children are null and the recursion bottoms out there naturally.

3. Solution Paths

Approach 1 — Rebuild a new tree (brute force)

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode copy = new TreeNode(root.val);
    copy.left  = invertTree(root.right);     // new left comes from the old right
    copy.right = invertTree(root.left);
    return copy;
}

Allocate a fresh tree rather than mutating the input.

• Time O(n) · Space O(n) for the new nodes, plus O(h) stack

Counter-questions on this approach

⭐ "Why allocate n new nodes when you could swap two pointers?"

No reason, for this problem. Inverting is a permutation of existing structure — no node's value changes, only which parent slot it sits in. Rebuilding does n allocations to achieve what n pointer swaps achieve for free.

"Is there ever a reason to prefer it?"

Yes — when the caller still needs the original. In-place inversion destroys it. If the tree were shared, or if the method were meant to be pure, this is the correct version. Worth asking whether mutation is acceptable rather than assuming.

"Is the extra space really O(n), or O(h)?"

Both apply, for different reasons: O(n) for the allocated nodes, plus O(h) for the recursion stack. The in-place version drops the first and keeps the second.

Approach 2 — Recursive swap in place (optimal)

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    TreeNode temp = root.left;      // save one side before overwriting
    root.left  = root.right;
    root.right = temp;

    invertTree(root.left);
    invertTree(root.right);
    return root;
}

• Time O(n) — every node visited once · Space O(h) stack, which is O(log n) balanced and O(n) degenerate

Counter-questions on this approach

⭐ "Could you swap after the recursive calls instead of before?"

Yes, and the result is identical. The swap at a node doesn't alter the contents of either subtree — only which slot each occupies — so the two operations commute.

That's worth flagging as unusual. In Diameter or Max Path Sum the parent's work depends on values returned by the children, so the recursion must finish first. Here it genuinely doesn't matter, and knowing why is more useful than knowing that.

"Why do you need the temporary variable?"

Same reason as the linked list questions: root.left = root.right destroys the only reference to the old left subtree. Save it first. It's the same discipline, one level up.

"What's the actual space complexity?"

O(h) for the call stack, where h is the height. Balanced, that's O(log n); a degenerate tree that's effectively a linked list makes it O(n). At n <= 100 it's irrelevant, but the distinction matters for the deeper trees in questions 14 and 15.

"Does it handle a single node, or a node with one child?"

Yes, with no special case. A single node swaps null with null. A node with only a left child swaps it into the right slot and recurses into two subtrees, one of which is null and returns immediately.

Approach 3 — Iterative with an explicit queue (BFS)

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        TreeNode temp = node.left;
        node.left  = node.right;
        node.right = temp;

        if (node.left  != null) q.offer(node.left);
        if (node.right != null) q.offer(node.right);
    }
    return root;
}

• Time O(n) · Space O(w) where w is the maximum width

Counter-questions on this approach

⭐ "Same complexity. Why would you write this instead?"

To avoid the call stack. On a degenerate tree the recursion is O(n) deep and can overflow; this version's memory is O(w), the widest level. Which is better depends on the tree's shape — a deep skinny tree favours the queue, a wide shallow tree favours recursion.

At n <= 100 neither matters. I'd write the recursive one for clarity and mention this as the answer if stack depth were a concern.

"Does it have to be a queue? Could you use a stack?"

Yes — a Deque used as a stack gives DFS instead of BFS, and the result is identical. Because the swaps are independent, visit order is irrelevant here. That's another consequence of the independence noted above, and it's a good check of whether someone understood it.

"Why LinkedList for the queue?"

It implements Queue and allows nulls, though I never enqueue null here. ArrayDeque is faster and is the better default — it just forbids null elements. See 02.

Comparison

4. Why the Optimal Wins

All three are O(n) — you must touch every node, since every node's children get swapped. The separation is space.

Rebuilding allocates n nodes to express a permutation of pointers, which two assignments per node achieve directly.

Between recursion and the explicit queue, it's a genuine trade: O(h) versus O(w). Recursion is shorter and clearer, so it's the default unless the tree is known to be deep.

The framing worth keeping:

State the recursive contract — "this call mirrors the subtree below it" — then assume it holds for the children and do only the node's own work.

That's the template for every question in this section. The variation is what "the node's own work" is and what gets returned.

5. Java Prerequisites

The node

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val; this.left = left; this.right = right;
    }
}

The recursion skeleton — memorize this shape:

ReturnType solve(TreeNode node) {
    if (node == null) return base;         // empty tree
    ReturnType L = solve(node.left);
    ReturnType R = solve(node.right);
    return combine(node, L, R);
}

Every question in this section is a choice of base, combine, and ReturnType.

Swapping references

TreeNode temp = a;  a = b;  b = temp;

Java has no tuple assignment, so the temporary is mandatory.

BFS with a queue

Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) { TreeNode n = q.poll(); ... }

6. Interview Communication Guide

Clarifying questions: Mutate in place or return a new tree (in place is expected)? Can the root be null (yes)? Is recursion acceptable, or is O(1)/iterative wanted (ask if the tree could be deep)?

The pitch

"Inverting means mirroring, and mirroring a tree is just swapping the two children — at every node, not only at the root.

I'd state the recursive contract first: invert(node) mirrors the subtree below it. Assuming that holds for the children, mirroring a node is one swap of its two child pointers, plus recursing into both.

Base case is null — the mirror of an empty tree is an empty tree — and leaves fall out of that automatically.

O(n) time since every node is touched once, and O(h) space for the call stack — O(log n) balanced, O(n) if the tree is degenerate.

One thing worth noting: here the swap and the recursion can happen in either order, because swapping a node's children doesn't change what's inside those subtrees. That's unusual — in Diameter or Max Path Sum the parent depends on values the children return, so the order is forced. Recognising which kind of problem you have is the useful part.

If stack depth were a concern I'd do it iteratively with a queue, which is O(w) instead."

Edge cases to volunteer:

Name the one-child case. It's where a swap that "looks like nothing happened" actually moves a subtree, and it catches implementations that guard the recursion with if (node.left != null && node.right != null).

7. Follow-Up Questions — Modified Constraints

⭐ "Check whether a tree is symmetric — a mirror of itself."

LeetCode 101, and a genuinely different problem. You don't invert; you compare two subtrees in opposite directions: mirror(a.left, b.right) && mirror(a.right, b.left). Inverting one half and comparing would work but mutates the input for no reason.

"Invert only the bottom k levels."

Pass the depth down and swap only when depth >= h - k, which means computing the height first — two passes. The recursion carries an extra parameter; the body is unchanged.

"What if the tree were n-ary rather than binary?"

Reverse the children list at every node instead of swapping two pointers: Collections.reverse(node.children). Same structure, O(n) overall since each child appears in exactly one list.

"Do it without recursion and without extra memory."

Not possible in general — you need to remember where to return to, which is O(h) at minimum. Morris traversal achieves O(1) by temporarily rewiring the tree, but it relies on inorder threading and doesn't adapt cleanly to a structural mutation like this one. I'd say plainly that O(h) is the floor rather than pretend otherwise.

"What if nodes had parent pointers?"

The swap must also fix the children's parent fields — and since the parent doesn't change, only the slot, nothing actually needs updating. Worth pausing on: parent pointers survive inversion untouched, which is a small surprise and a good sanity check on whether you understand what inverting does.