206. Invert Binary Tree
Your function receives the root of a binary tree and must return the root of its mirror image: at every single node, the left and right children trade places. Each node exposes val, left, and right (a missing child is None/null).
Swapping only the root's two children is not enough — the exchange has to happen at every level, all the way down. The tree famously fits on a whiteboard in four lines, yet it trips people up when they mutate a child pointer before the other side has been handled. Return the same root you were given (the structure is modified in place).
Example 1:
Input: root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]
Explanation: Every pair of siblings swaps: 2 and 7 trade places under the root, then (1, 3) and (6, 9) swap inside their new subtrees.
Example 2:
Input: root = [2, 1, 3]
Output: [2, 3, 1]
Explanation: One swap at the root mirrors the whole three-node tree.
Example 3:
Input: root = [1, 2]
Output: [1, null, 2]
Explanation: Node 2 moves from the root's left side to its right side, leaving the left slot empty.
Constraints:
- 0 ≤ number of nodes ≤ 100
- -100 ≤ node value ≤ 100
Hints:
Think about what inverting means for one node in isolation: its left and right pointers swap. The rest of the job is just making sure that happens at every node exactly once.
Recursively: invert the left subtree, invert the right subtree, then swap the two — or swap first and recurse after; both orders work as long as you don't lose a pointer. In Python, simultaneous assignment (a tuple swap) sidesteps the temporary variable.
No recursion required: any traversal that visits every node works. Push nodes onto a queue or stack, swap each node's children as it comes off, and enqueue the (already swapped) children.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [4, 2, 7, 1, 3, 6, 9]
Expected output: [4, 7, 2, 9, 6, 3, 1]