Invert Binary Tree

Problem

UI component trees, directory mirrors, and network topology backups all require producing a mirror image of a hierarchical structure. Given the root of a binary tree, invert the tree by swapping left and right children at every node, and return the root.

Example 1:

Input: root = [5,3,8,1,4,7,10]
Output: [5,8,3,10,7,4,1]
Explanation: every node's left and right children are swapped, mirroring the tree.

    5               5
   / \             / \
  3   8    →      8   3
 / \ / \         / \ / \
1  4 7 10      10  7 4  1

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [2,1,4]
Output: [2,4,1]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution Breakdown

Approach - Recursive DFS with a local child swap.

Inverting a tree means mirroring it: at every node, the left and right children trade places. The insight that makes this trivial is that the swap is purely local - a node only needs to exchange its own two child pointers, and the recursion handles every deeper level independently. So the body is three moves: swap root.left and root.right, recurse into both (now-swapped) children, and return root. The base case root is None returns None, which also means the recursive calls on leaves' missing children stop cleanly.

The Python idiom root.left, root.right = root.right, root.left is what makes the swap safe without a temporary: the right-hand side is fully evaluated before either assignment, so no pointer is clobbered mid-swap. Trace 5 -> (3 -> (1, 4), 8 -> (7, 10)). At the root, children 3 and 8 swap, so 8 is now on the left. Recursing into 8, its children 7 and 10 swap to give 8 -> (10, 7). Recursing into 3, its children 1 and 4 swap to 3 -> (4, 1). The result is the full mirror 5 -> (8 -> (10, 7), 3 -> (4, 1)). Note the swap can run before or after the recursive calls - preorder or postorder both work, because each swap depends on nothing but the node itself.

Edge cases - A None root returns None immediately. A single node returns unchanged, since swapping two None children is a no-op.

Complexity - O(n) time, O(h) space - each node is visited once and swapped in O(1), with the recursion stack reaching the tree's height.