226. Invert Binary Tree

Quick Identifier

• Topic: trees
• Pattern: Tree DFS
• Difficulty: Easy
• Companies: Google, Amazon, Apple, Meta, Bloomberg
• Frequency: Very High
• LeetCode: 226

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(h) from the optimal approach.
• Core Mechanism: Given the root of a binary tree, swap every node’s left and right subtrees so the tree is mirrored left-to-right. Return the new root.

Concept Explanation

Given the root of a binary tree, swap every node’s left and right subtrees so the tree is mirrored left-to-right. Return the new root.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• "Invert" / "flip" / "mirror" the binary tree
• Swap left and right children at every node
• Same structure, mirrored geometry

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — O(n) time / O(n) space — copy tree into new mirrored structure (unnecessary allocation).
• Better — O(n) time / O(n) space — BFS level-by-level, swap children at each dequeue (same asymptotics, queue overhead).
• Optimal — O(n) time / O(h) space recursion stack — DFS post-order or pre-order: swap Left and Right, recurse.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = root.Right, root.Left
	invertTree(root.Left)
	invertTree(root.Right)
	return root
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function invertTree(root) {
	if (root === null) {
		return null;
	}
	[root.left, root.right] = [root.right, root.left];
	invertTree(root.left);
	invertTree(root.right);
	return root;
}

Walkthrough

Input: a small tree root = 4 / 2,7 / 1,3,6,9

Invariant: after processing a node, its immediate children are swapped; recursion completes the mirror for all descendants.

Edge Cases

• Empty tree (null) → return null
• Single node → swap still fine; tree unchanged shape
• Skewed chain → still linear time; stack depth O(n)

Pitfalls

• Forgetting to recurse after swapping (only top level flips)
• Returning a new tree when the problem expects in-place mutation of links

Similar Problems

• 100. Same Tree — compare structures; invert plus compare relates to mirroring.
• 572. Subtree of Another Tree — matching subtrees with DFS helper patterns.
• 104. Maximum Depth of Binary Tree — same recursive tree traversal template.

Variants

• Invert n-ary tree → swap list of children in reverse order at each node.
• Return new inverted copy without mutating input → clone while swapping.
• "Mirror equals original" check → same as symmetric tree (not in this batch) using two pointers from left and right subtrees.

Mind-Map Tags

#trees #dfs #invert #mirror #swap-children