Invert Binary Tree

Invert a binary tree — mirror it left to right — and return its root.

A way to picture it

Hold a family photo up to a mirror. Every parent still has the same two children, just swapped sides. Walk the tree, tell every node to swap its kids, and the whole picture flips.

How to approach it

Swap each node's left and right children, then invert both subtrees. Every node is swapped exactly once.

Example

Input: {"root":[4,2,7,1,3,6,9]}. Output: [4,7,2,9,6,3,1].

Complexity: O(n) time and O(h) space. One swap per node; recursion depth is the height.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.