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.

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

Solution

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 4 -> (2 -> (1, 3), 7 -> (6, 9)). At the root, children 2 and 7 swap, so 7 is now on the left. Recursing into 7, its children 6 and 9 swap to give 7 -> (9, 6). Recursing into 2, its children 1 and 3 swap to 2 -> (3, 1). The result is the full mirror 4 -> (7 -> (9, 6), 2 -> (3, 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.