Invert binary tree

Given the root of a binary tree, invert it so that it becomes its mirror image, and return its root.

Before you code

Every node needs the same change: its two children swap places. Any traversal that visits every node once works; what matters is not losing a child pointer mid-swap.

Hints

1. Swap node.left and node.right, then recurse into both.
2. Preorder and postorder both work. Inorder needs care: after the swap, the subtree you already processed is now on the right.
3. A level-order version with a queue avoids recursion on very deep trees.

Production & complexity notes

When solving Invert binary tree on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Vocabulary and traversals to reinforce the underlying pattern.

What it practices

Visiting every node with a traversal, from Vocabulary and traversals.