Invert Binary Tree
EasySwap children everywhere
Swap every node's left and right children to mirror the whole tree.
The idea
Mirror the tree by swapping every node's left and right children, recursively. A three-line classic.
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.