Invert Binary Tree

Problem

You are given the root of a binary tree. Produce its mirror image: for every node in the tree, the left and right subtrees trade places. Do the transformation in place, reusing the existing nodes, and return the root.

• The tree has at most 2,000 nodes.
• Node values are small integers in the range -500 to 500; duplicates are allowed.
• The input may be empty (root is None), in which case return None.

Examples

• root = [5, 3, 8, 1, 4, None, 9] → [5, 8, 3, 9, None, 4, 1]. The root keeps its value; its two subtrees swap, and inside each of them the children swap again, so 8's lone right child 9 becomes a lone left child.
• root = [7, 2, 11] → [7, 11, 2]. Only one swap is needed at the root.
• root = [] → []. Nothing to invert.

(Lists are level-order with None marking a missing child, the usual convention in this guide.)

Hints

1. Look at the root by itself. What has to happen to its two child pointers, regardless of what is underneath them?
2. Suppose both subtrees were already mirrored. What work remains at the current node?
3. A depth-first traversal that swaps left and right at every node is the whole algorithm; recursion handles the subtrees.