20. Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.
How It Works & Algorithmic Design
Solves using Recursive Node Child Swapping:
- Base Case: If
root === null, returnnull. - Swap Children: Swap
root.leftandroot.rightusing a temporary variable. - Recursive Step:
invertTree(root.left).invertTree(root.right).
- Return: Return
rootafter children are inverted.
Why This Approach Works Best
Recursively mirroring left and right pointers in-place converts a binary tree into its mirror image in $O(n)$ time and $O(h)$ space.
Example Walkthrough
Input Tree:
[4, 2, 7, 1, 3, 6, 9]Original binary tree.
Inverted Output:
[4, 7, 2, 9, 6, 3, 1]Mirrored binary tree.
Answer: Invert binary tree implementation
function invertTree(root) {
if (!root) return null;
const temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}💡 Swap left and right child pointers recursively for all tree nodes.
Key Takeaways
- Swaps left and right pointers at every level.
- Can also be solved iteratively using Breadth-First Search (BFS) with a queue.
- Linear time complexity $O(n)$.