Loading…

easyTreesLC #226Frequently asked

Invert Binary Tree

Q: How do you solve Invert Binary Tree using the Recursive DFS — Swap and Recurse (Optimal) approach?

When to use it: Start here. It's the cleanest possible solution and shows you grasp the recursive structure immediately. Inverting a tree is the same simple action repeated everywhere: at each node, exchange its two children. Do that at every node and the whole tree becomes its mirror. **The recursive structure.** Handle the null node first (an empty subtree inverts to nothing). For a real node, swap `node.left` and `node.right`, then recursively invert both subtrees. That's it — the recursion guarantees the swap reaches every level, and the per-node swap guarantees each level is mirrored. **Why the order of the two recursive calls doesn't matter.** Inverting the left subtree and inverting the right subtree touch disjoint sets of nodes, so they're fully independent. You can swap first then recurse, or recurse first then swap, or recurse left before right or right before left — every combination produces the identical mirrored tree. This is a nice point to state out loud because it shows you reason about *independence* rather than just pattern-matching code. **Java vs Python swap.** Java has no tuple unpacking, so you stash one child in a `temp` variable before overwriting. Python lets you write `node.left, node.right = node.right, node.left` — and you can even fold the recursion into the same line: `node.left, node.right = invert(node.right), invert(node.left)`. Both are correct; the Python one-liner is a small flourish worth knowing. **The lore.** This is the problem behind the famous tweet — Homebrew's creator was reportedly rejected by Google for being unable to invert a binary tree on a whiteboard. The takeaway for you: it's genuinely easy, but only if you've internalized the swap-and-recurse template, so don't let nerves turn four lines into a struggle. Time complexity: O(n). Space complexity: O(h).

Q: How do you solve Invert Binary Tree using the Iterative BFS/DFS — Swap with a Queue or Stack approach?

When to use it: Offer when asked for an iterative version or when the tree could be deep enough to overflow the recursion stack. The iterative version makes the traversal container explicit instead of relying on the call stack. The per-node work is identical: swap the node's two children. **BFS with a queue.** Seed a queue with the root. While the queue is non-empty, dequeue a node, swap its `left` and `right`, and enqueue both children if they exist. This processes the tree level by level, mirroring each node as it's visited. **DFS with a stack.** Identical, but use a stack (LIFO) instead of a queue (FIFO). The traversal order differs, but since every node gets swapped exactly once and the swaps are independent, the final mirrored tree is the same. **Why pick this over recursion.** Two reasons to mention: (1) the recursion depth on a degenerate (linked-list-shaped) tree could be O(n) and overflow the call stack in languages with small stack limits, and (2) some interviewers explicitly ask 'can you do it without recursion?' to confirm you understand recursion is just a managed stack. Functionally the two solutions are equivalent in time and asymptotic space. Time complexity: O(n). Space complexity: O(n).

LCPractice

Trees & BST · 3 of 41 · 7 min

Given the root of a binary tree, invert the tree, and return its root.

Inverting means producing the mirror image: for every node, its left and right subtrees are swapped.

In plain English

Transform the tree in place (or rebuild it) so it becomes its own mirror image. Every node keeps its value; only the left/right child pointers are swapped, all the way down. Return the same root.

Examples

Example 1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Note: Every node's children swap: under 4, the 2 and 7 subtrees switch sides; under each, their children switch too.

Example 2

Input: root = [2,1,3]
Output: [2,3,1]
Note: The root keeps value 2; its children 1 and 3 swap places.

Example 3

Input: root = []
Output: []
Note: An empty tree is its own mirror — nothing to swap.

Constraints

The number of nodes is in the range [0, 100]
-100 ≤ Node.val ≤ 100
An empty tree inverts to an empty tree

Clarifying questions4First question: Should I mutate the input tree in place or return a new tree?Explore questions

Q1.Should I mutate the input tree in place or return a new tree?
In place is standard and expected here — we swap pointers and return the same root. Mention you could clone first if the caller must keep the original.
Q2.Can the tree be empty?
Yes — node count can be 0. The null base case handles it: inverting an empty tree returns null.
Q3.Does the order of recursive calls matter?
No. Inverting the left subtree and inverting the right subtree are independent, so either order yields the same result.
Q4.Recursive or iterative?
Lead with recursive (cleanest). Offer the iterative BFS (queue) or DFS (stack) version since it's a natural follow-up and avoids deep call stacks.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Mirror the tree: at every node, swap its left and right children. The recursive answer is four lines — swap the two child pointers, then recurse into both subtrees (order doesn't matter). The iterative answer does the same swap while walking the tree with a queue (BFS) or stack (DFS). Both are O(n) time, O(h) space. This is the famous problem Max Howell reportedly bombed at a Google interview.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can translate 'mirror the tree' into a clean recursive mutation that both swaps children and recurses, and whether you can produce an iterative equivalent on request.

Where candidates slip

Swapping the children but forgetting to recurse (only the top level mirrors), or recursing but forgetting to actually swap (nothing changes).

How to stand out

Note that the recursion order is irrelevant, show the one-line Python tuple swap, and offer the iterative BFS/DFS version to demonstrate you understand recursion is interchangeable with an explicit queue/stack.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive DFS — Swap and Recurse (Optimal)Optimal	`O(n)`	`O(h)`	Start here. It's the cleanest possible solution and shows you grasp the recursive structure immediately.	Read
2	Iterative BFS/DFS — Swap with a Queue or Stack	`O(n)`	`O(n)`	Offer when asked for an iterative version or when the tree could be deep enough to overflow the recursion stack.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMirror the treeRecursion or explicit container?RecursionExplicitExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Recursive DFS — Swap and Recurse (Optimal)

TimeO(n)SpaceO(h)

Start here. It's the cleanest possible solution and shows you grasp the recursive structure immediately.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What single operation, applied at every node, turns a tree into its mirror image?

2Hint 2Explore hint

At each node, swap its left and right child pointers. Then you still need to mirror the contents of each subtree — how do you reach them?

3Hint 3Explore hint

Swap the children, then recurse into both subtrees (order doesn't matter). Base case: a null node returns null.

A · Core idea

Inverting a tree is the same simple action repeated everywhere: at each node, exchange its two children. Do that at every node and the whole tree becomes its mirror.

The recursive structure. Handle the null node first (an empty subtree inverts to nothing). For a real node, swap node.left and node.right, then recursively invert both subtrees. That's it — the recursion guarantees the swap reaches every level, and the per-node swap guarantees each level is mirrored.

Why the order of the two recursive calls doesn't matter. Inverting the left subtree and inverting the right subtree touch disjoint sets of nodes, so they're fully independent. You can swap first then recurse, or recurse first then swap, or recurse left before right or right before left — every combination produces the identical mirrored tree. This is a nice point to state out loud because it shows you reason about independence rather than just pattern-matching code.

Java vs Python swap. Java has no tuple unpacking, so you stash one child in a temp variable before overwriting. Python lets you write node.left, node.right = node.right, node.left — and you can even fold the recursion into the same line: node.left, node.right = invert(node.right), invert(node.left). Both are correct; the Python one-liner is a small flourish worth knowing.

The lore. This is the problem behind the famous tweet — Homebrew's creator was reportedly rejected by Google for being unable to invert a binary tree on a whiteboard. The takeaway for you: it's genuinely easy, but only if you've internalized the swap-and-recurse template, so don't let nerves turn four lines into a struggle.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,7,1,3,6,9]

Before vs after on [2,1,3]

How to read it:The root keeps value 2; children 1 and 3 trade sides.

Rendering diagram…

Final result[4,7,2,9,6,3,1]

C · Code with teaching comments

solution.javaJava

Recursive DFS — Swap and Recurse (Optimal) — optimal

5 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public TreeNode invertTree(TreeNode root) {
10
    if (root == null) return null;       // base case
11
    TreeNode temp = root.left;           // stash left
12
    root.left = root.right;              // right becomes left
13
    root.right = temp;                   // stashed left becomes right
14
    invertTree(root.left);               // recurse (order irrelevant)
15
    invertTree(root.right);
16
    return root;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Two things must both happen at every node: the swap (which mirrors this level) and the recursion (which carries the swap downward). Drop either and you get a no-op or a one-level flip. Saying 'swap AND recurse, both required' out loud is the quickest way to prove you understand why it works.

ComplexityO(n) time, O(h) space — Each of the n nodes is visited once and does an O(1) pointer swap → O(n) time. Recursion depth equals the height h → O(h) space, ranging from O(log n) balanced to O(n) for a skewed tree.

E · Edge cases and pitfalls6root = [] — Base case fires immediately → returns null.Explore edge cases

Edge cases handled

root = []Base case fires immediately → returns null.
root = [1] (single node)No children to swap; both recursive calls hit null → returns the node unchanged.
Left-skewed tree [1,2,null,3]Becomes right-skewed — the chain flips direction entirely.

Pitfalls

Recursing without swapping (or swapping without recursing) — one mirrors nothing, the other mirrors only the root.
In Java, assigning root.left = root.right before saving the old left — you lose the left subtree.
Forgetting to return root — LeetCode expects the (same) root back.

03.2

Approach 2 of 2

Iterative BFS/DFS — Swap with a Queue or Stack

TimeO(n)SpaceO(n)

Offer when asked for an iterative version or when the tree could be deep enough to overflow the recursion stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recursion just uses a hidden stack. What explicit container could you use to visit every node and swap its children?

2Hint 2Explore hint

Push the root into a queue (BFS) or stack (DFS). Repeatedly pop a node, swap its two children, then push the non-null children.

3Hint 3Explore hint

It doesn't matter whether you swap before or after pushing the children, as long as you push whatever ends up in the left/right slots so they get processed too.

A · Core idea

The iterative version makes the traversal container explicit instead of relying on the call stack. The per-node work is identical: swap the node's two children.

BFS with a queue. Seed a queue with the root. While the queue is non-empty, dequeue a node, swap its left and right, and enqueue both children if they exist. This processes the tree level by level, mirroring each node as it's visited.

DFS with a stack. Identical, but use a stack (LIFO) instead of a queue (FIFO). The traversal order differs, but since every node gets swapped exactly once and the swaps are independent, the final mirrored tree is the same.

Why pick this over recursion. Two reasons to mention: (1) the recursion depth on a degenerate (linked-list-shaped) tree could be O(n) and overflow the call stack in languages with small stack limits, and (2) some interviewers explicitly ask 'can you do it without recursion?' to confirm you understand recursion is just a managed stack. Functionally the two solutions are equivalent in time and asymptotic space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,7,1,3,6,9] (BFS with a queue)

pop 4

swap → 4:[7,2]; enqueue 7,2

Statequeue=[7,2]

Final result[4,7,2,9,6,3,1]

C · Code with teaching comments

Reference implementation previewpublic TreeNode invertTree(TreeNode root) { if (root == null) return null; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) {Explore the full code

solution.javaJava

Iterative BFS/DFS — Swap with a Queue or Stack — reference

4 teaching notes

1
public TreeNode invertTree(TreeNode root) {
2
    if (root == null) return null;
3
    Queue<TreeNode> queue = new LinkedList<>();
4
    // Seed the BFS with the root node.
5
    queue.offer(root);
6
    while (!queue.isEmpty()) {
7
        // Process one node per loop iteration.
8
        TreeNode node = queue.poll();
9
        TreeNode temp = node.left;        // swap children
10
        // Mid-swap — temp already holds the original left so nothing is lost.
11
        node.left = node.right;
12
        node.right = temp;
13
        // Enqueue children so they get swapped too; skip nulls to keep the queue clean.
14
        if (node.left != null) queue.offer(node.left);
15
        if (node.right != null) queue.offer(node.right);
16
    }
17
    return root;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Recursion and an explicit stack are interchangeable; swapping a queue for that stack just changes the visiting order from depth-first to breadth-first. Since the swap at each node is independent of every other, the order you visit nodes never affects the result — only whether you visit them all.

ComplexityO(n) time, O(n) space — Each node is enqueued/pushed and processed exactly once with an O(1) swap → O(n) time. A BFS queue can hold up to the tree's maximum width (O(n) in the worst level); a DFS stack holds up to O(h). Worst-case extra space is O(n).

E · Edge cases and pitfalls6root = [] — Guard returns null before the queue is touched.Explore edge cases

Edge cases handled

root = []Guard returns null before the queue is touched.
Perfectly balanced treeQueue peaks at ~n/2 nodes (the last level) → O(n) space, the BFS worst case.
Skewed treeQueue holds at most 1-2 nodes at a time → effectively O(1) extra space for BFS here, vs O(n) recursion depth for DFS.

Pitfalls

Enqueuing null children — clutters the queue and can cause null dereferences depending on the guard.
Forgetting the empty-tree guard before seeding the queue.
Assuming BFS and DFS give different trees — they don't; only the visiting order differs.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Swap without recursion (only one level flips)

Swapping just the root's two children mirrors a single level. Without recursing, every deeper level keeps its original orientation.

Explore the code comparison

Don't write this

def invertTree(self, root):
    if not root:
        return None
    root.left, root.right = root.right, root.left  # only the root is mirrored
    return root

Write this instead

def invertTree(self, root):
    if not root:
        return None
    root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
    return root

Java swap without a temp variable

Assigning root.left = root.right first overwrites the left pointer, so the subsequent root.right = root.left just copies the right subtree onto both sides — the original left subtree is lost.

Explore the code comparison

Don't write this

root.left = root.right;   // original left is now unreachable
root.right = root.left;   // copies right onto right — both subtrees identical

Write this instead

TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Recursive mirror — swap children at every node

Code pattern to memorize

invert(node):
    if node is null: return null
    node.left, node.right = invert(node.right), invert(node.left)
    return node

Rules to remember

1The whole problem is one operation: swap left and right at every node.
2Recurse and swap — visiting without swapping does nothing; swapping only the root mirrors one level.
3In Java you need a temp variable to swap; in Python use tuple unpacking and you can swap and recurse in one line.
4Order of the two recursive calls is irrelevant — each subtree's inversion is independent.
5Iterative BFS/DFS works identically: pop a node, swap its children, push both children.

Use this pattern when

You must produce the mirror image of a tree
Any per-node structural transformation that recurses into both subtrees
Warm-up to confirm you can write a clean recursive tree mutation

Choose another pattern when

You must compare two trees, not transform one → Same Tree / Symmetric Tree
Only values change, not structure → a plain traversal suffices
The tree is a BST and order must be preserved → inverting destroys the BST property

Interview takeaway

Invert Binary Tree is the canonical 'recurse into both children and do one thing per node' problem. The 'one thing' here is swapping the two child pointers. Master the shape and you have the template for half of all easy tree questions.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPer-node structural mutation via DFS: do one O(1) operation at every node and recurse into both children. Here the operation is a child swap. The same skeleton (recurse both sides, do one thing per node) drives Maximum Depth, Same Tree, and most easy tree problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Symmetric Tree
Don't invert — instead check whether the tree is a mirror of itself by comparing left and right subtrees in mirror order.
Same Tree
Parallel DFS comparing two trees node-by-node — the comparison cousin of this transformation.
Flip Equivalent Binary Trees
Coming soon
Two trees are flip-equivalent if a series of these child swaps makes them identical.
Maximum Depth of Binary Tree
Same recurse-into-both-children skeleton, aggregating heights instead of swapping.

Same pattern

←

Validate Binary Search Tree

Continue · Next problem

Maximum Depth of Binary Tree

easyTreesLC #226Frequently asked

Invert Binary Tree

LCPractice

Trees & BST · 3 of 41 · 7 min

Given the root of a binary tree, invert the tree, and return its root.

Inverting means producing the mirror image: for every node, its left and right subtrees are swapped.

In plain English

Transform the tree in place (or rebuild it) so it becomes its own mirror image. Every node keeps its value; only the left/right child pointers are swapped, all the way down. Return the same root.

Examples

Example 1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Note: Every node's children swap: under 4, the 2 and 7 subtrees switch sides; under each, their children switch too.

Example 2

Input: root = [2,1,3]
Output: [2,3,1]
Note: The root keeps value 2; its children 1 and 3 swap places.

Example 3

Input: root = []
Output: []
Note: An empty tree is its own mirror — nothing to swap.

Constraints

The number of nodes is in the range [0, 100]
-100 ≤ Node.val ≤ 100
An empty tree inverts to an empty tree

Clarifying questions4First question: Should I mutate the input tree in place or return a new tree?Explore questions

Q1.Should I mutate the input tree in place or return a new tree?
In place is standard and expected here — we swap pointers and return the same root. Mention you could clone first if the caller must keep the original.
Q2.Can the tree be empty?
Yes — node count can be 0. The null base case handles it: inverting an empty tree returns null.
Q3.Does the order of recursive calls matter?
No. Inverting the left subtree and inverting the right subtree are independent, so either order yields the same result.
Q4.Recursive or iterative?
Lead with recursive (cleanest). Offer the iterative BFS (queue) or DFS (stack) version since it's a natural follow-up and avoids deep call stacks.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can translate 'mirror the tree' into a clean recursive mutation that both swaps children and recurses, and whether you can produce an iterative equivalent on request.

Where candidates slip

Swapping the children but forgetting to recurse (only the top level mirrors), or recursing but forgetting to actually swap (nothing changes).

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive DFS — Swap and Recurse (Optimal)Optimal	`O(n)`	`O(h)`	Start here. It's the cleanest possible solution and shows you grasp the recursive structure immediately.	Read
2	Iterative BFS/DFS — Swap with a Queue or Stack	`O(n)`	`O(n)`	Offer when asked for an iterative version or when the tree could be deep enough to overflow the recursion stack.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Recursive DFS — Swap and Recurse (Optimal)

TimeO(n)SpaceO(h)

Start here. It's the cleanest possible solution and shows you grasp the recursive structure immediately.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What single operation, applied at every node, turns a tree into its mirror image?

2Hint 2Explore hint

At each node, swap its left and right child pointers. Then you still need to mirror the contents of each subtree — how do you reach them?

3Hint 3Explore hint

Swap the children, then recurse into both subtrees (order doesn't matter). Base case: a null node returns null.

A · Core idea

Inverting a tree is the same simple action repeated everywhere: at each node, exchange its two children. Do that at every node and the whole tree becomes its mirror.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,7,1,3,6,9]

Before vs after on [2,1,3]

How to read it:The root keeps value 2; children 1 and 3 trade sides.

Rendering diagram…

Final result[4,7,2,9,6,3,1]

C · Code with teaching comments

solution.javaJava

Recursive DFS — Swap and Recurse (Optimal) — optimal

5 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public TreeNode invertTree(TreeNode root) {
10
    if (root == null) return null;       // base case
11
    TreeNode temp = root.left;           // stash left
12
    root.left = root.right;              // right becomes left
13
    root.right = temp;                   // stashed left becomes right
14
    invertTree(root.left);               // recurse (order irrelevant)
15
    invertTree(root.right);
16
    return root;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6root = [] — Base case fires immediately → returns null.Explore edge cases

Edge cases handled

root = []Base case fires immediately → returns null.
root = [1] (single node)No children to swap; both recursive calls hit null → returns the node unchanged.
Left-skewed tree [1,2,null,3]Becomes right-skewed — the chain flips direction entirely.

Pitfalls

Recursing without swapping (or swapping without recursing) — one mirrors nothing, the other mirrors only the root.
In Java, assigning root.left = root.right before saving the old left — you lose the left subtree.
Forgetting to return root — LeetCode expects the (same) root back.

03.2

Approach 2 of 2

Iterative BFS/DFS — Swap with a Queue or Stack

TimeO(n)SpaceO(n)

Offer when asked for an iterative version or when the tree could be deep enough to overflow the recursion stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recursion just uses a hidden stack. What explicit container could you use to visit every node and swap its children?

2Hint 2Explore hint

Push the root into a queue (BFS) or stack (DFS). Repeatedly pop a node, swap its two children, then push the non-null children.

3Hint 3Explore hint

It doesn't matter whether you swap before or after pushing the children, as long as you push whatever ends up in the left/right slots so they get processed too.

A · Core idea

The iterative version makes the traversal container explicit instead of relying on the call stack. The per-node work is identical: swap the node's two children.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,7,1,3,6,9] (BFS with a queue)

pop 4

swap → 4:[7,2]; enqueue 7,2

Statequeue=[7,2]

Final result[4,7,2,9,6,3,1]

C · Code with teaching comments

solution.javaJava

Iterative BFS/DFS — Swap with a Queue or Stack — reference

4 teaching notes

1
public TreeNode invertTree(TreeNode root) {
2
    if (root == null) return null;
3
    Queue<TreeNode> queue = new LinkedList<>();
4
    // Seed the BFS with the root node.
5
    queue.offer(root);
6
    while (!queue.isEmpty()) {
7
        // Process one node per loop iteration.
8
        TreeNode node = queue.poll();
9
        TreeNode temp = node.left;        // swap children
10
        // Mid-swap — temp already holds the original left so nothing is lost.
11
        node.left = node.right;
12
        node.right = temp;
13
        // Enqueue children so they get swapped too; skip nulls to keep the queue clean.
14
        if (node.left != null) queue.offer(node.left);
15
        if (node.right != null) queue.offer(node.right);
16
    }
17
    return root;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6root = [] — Guard returns null before the queue is touched.Explore edge cases

Edge cases handled

root = []Guard returns null before the queue is touched.
Perfectly balanced treeQueue peaks at ~n/2 nodes (the last level) → O(n) space, the BFS worst case.
Skewed treeQueue holds at most 1-2 nodes at a time → effectively O(1) extra space for BFS here, vs O(n) recursion depth for DFS.

Pitfalls

Enqueuing null children — clutters the queue and can cause null dereferences depending on the guard.
Forgetting the empty-tree guard before seeding the queue.
Assuming BFS and DFS give different trees — they don't; only the visiting order differs.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Swap without recursion (only one level flips)

Swapping just the root's two children mirrors a single level. Without recursing, every deeper level keeps its original orientation.

Explore the code comparison

Don't write this

def invertTree(self, root):
    if not root:
        return None
    root.left, root.right = root.right, root.left  # only the root is mirrored
    return root

Write this instead

def invertTree(self, root):
    if not root:
        return None
    root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
    return root

Java swap without a temp variable

Assigning root.left = root.right first overwrites the left pointer, so the subsequent root.right = root.left just copies the right subtree onto both sides — the original left subtree is lost.

Explore the code comparison

Don't write this

root.left = root.right;   // original left is now unreachable
root.right = root.left;   // copies right onto right — both subtrees identical

Write this instead

TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Recursive mirror — swap children at every node

Code pattern to memorize

invert(node):
    if node is null: return null
    node.left, node.right = invert(node.right), invert(node.left)
    return node

Rules to remember

1The whole problem is one operation: swap left and right at every node.
2Recurse and swap — visiting without swapping does nothing; swapping only the root mirrors one level.
3In Java you need a temp variable to swap; in Python use tuple unpacking and you can swap and recurse in one line.
4Order of the two recursive calls is irrelevant — each subtree's inversion is independent.
5Iterative BFS/DFS works identically: pop a node, swap its children, push both children.

Use this pattern when

You must produce the mirror image of a tree
Any per-node structural transformation that recurses into both subtrees
Warm-up to confirm you can write a clean recursive tree mutation

Choose another pattern when

You must compare two trees, not transform one → Same Tree / Symmetric Tree
Only values change, not structure → a plain traversal suffices
The tree is a BST and order must be preserved → inverting destroys the BST property

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Symmetric Tree
Don't invert — instead check whether the tree is a mirror of itself by comparing left and right subtrees in mirror order.
Same Tree
Parallel DFS comparing two trees node-by-node — the comparison cousin of this transformation.
Flip Equivalent Binary Trees
Coming soon
Two trees are flip-equivalent if a series of these child swaps makes them identical.
Maximum Depth of Binary Tree
Same recurse-into-both-children skeleton, aggregating heights instead of swapping.

Same pattern

←

Validate Binary Search Tree

Continue · Next problem

Maximum Depth of Binary Tree