Invert Binary Tree
MediumSwap the children, everywhere
Problem
Invert a binary tree (mirror it): swap every node's left and right children.
Swap each node's two children, all the way down — the tree becomes its mirror image.
The idea
Swap each node's left and right child and recurse into both. Whether you swap before or after recursing makes no difference, which is a nice illustration that some traversals are order-independent.
The trick
- Null returns null — the base case handles empty subtrees.
- O(n) time, O(height) stack.
Step 1 of 4. To invert the tree, swap the left and right child of every node.
1/4
Optimal
timeO(n)spaceO(h)
Swap, then recurse.
1function invert(node) {2 if (!node) return null;3 [node.left, node.right] = [invert(node.right), invert(node.left)];4 return node;5}Input
- nodes
- 6, 5 edges
Memory
- swap
- —
Output
- done
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [4,2,7,1,3,6,9]
- Output:
- [[4], [7, 2], [9, 6, 3, 1]]
- Explanation:
- Every left/right pair is swapped.
Example 2
- Input:
- tree = [1,2]
- Output:
- [[1], [2]]
- Explanation:
- The single child flips sides.
Example 3
- Input:
- tree = []
- Output:
- []
- Explanation:
- Empty stays empty.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.