Invert a binary tree, so that it becomes its own mirror image. Every left child becomes a right child, and every right child becomes a left child.
DSA Animator › DSA Revision › Tree › Invert Binary Tree
Remember: swap the children, then recurse into both sides. A breadth first search with the same swap works too. The video solves Invert Binary Tree (LeetCode 226, Easy) with the DFS Swap pattern from the Tree topic, and you can replay every step in the interactive Invert Binary Tree animation.
Invert a binary tree, so that it becomes its own mirror image. Every left child becomes a right child, and every right child becomes a left child.
For the tree 4, 2, 7, 1, 3, 6, 9, the result is 4, 7, 2, 9, 6, 3, 1.
You might try to rebuild a new tree level by level in reverse order. But the mirror image is just one swap per node, so no new tree is needed.
At every node, swap its left and right child. Then invert the left subtree and the right subtree in the same way. A null node needs no work, so it is the base case. The order of the swap and the recursive calls does not matter, as long as every node is swapped exactly once.
At the root 4, swap its children, so 7 is now on the left and 2 on the right. Move into 7 and swap its children, so 9 is left and 6 is right. Move into 2 and swap its children, so 3 is left and 1 is right. The leaves have null children, so nothing changes there. Reading the result level by level gives 4, 7, 2, 9, 6, 3, 1.
In code, return null if the root is null. Store the left child in a temporary variable, then set left to the inverted right subtree. Set right to the inverted temporary, and return the root. Every node is visited once, so it's O of n time and O of the height in stack space.
Remember: swap the children, then recurse into both sides. A breadth first search with the same swap works too.