Invert Binary Tree
Asked at Google, Meta, Amazon, Microsoft, Apple
Problem
Given the root of a binary tree, invert the tree and return its root. Inverting means swapping every left and right child recursively. Made famous by the "would you invert a binary tree?" meme.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Apple | Easy | View all Apple questions → |
How to Think About It
Recursive approach: swap left and right children, then recurse on both subtrees. The base case is a null node.
Why it works: by swapping at every node, the entire tree becomes its mirror image. Left becomes right, right becomes left.
BFS alternative: use a queue, swap children at each node during level-order traversal. Same result, different traversal order.
Visual walkthrough for tree: 4
/ \n 2 7
/ / \n 1 3 6 9
Invert(4): swap → 4
Invert(2): swap → 2 Invert(7): swap → 7
Invert(1): swap → 1 Invert(3): swap → 3 Invert(6): swap → 6 Invert(9): swap → 9
Result: 4
/ \n 7 2
/ / \n 9 6 3 1
Edge cases: empty tree (return null), single node (return as-is), already inverted (same result).
Optimal Approach
Recursive DFS:
Step 1: Base case — if root is null, return null.
Step 2: Swap root.left and root.right.
Step 3: Recursively invert root.left and root.right.
Step 4: Return root.
The swap happens before recursion, so the entire subtree is inverted as we unwind.
Time: O(n) — visit every node once. Space: O(h) — recursion stack.
What Trips People Up in Real Interviews
Not handling the base case. If the node is null, return null. Without this, you'll get a null pointer exception.
Forgetting to recurse after swapping. You need to swap children AND then invert both subtrees.
Confusing "invert" with "mirror image." Inverting a binary tree means every left child becomes right and vice versa. The result is a mirror image.
Not handling a single node. A single node tree is already inverted — just return it.
Trying to invert by traversing and building a new tree. The problem says to invert in-place by swapping children. Don't create new nodes — just swap existing left and right pointers.
Solution Code
def invertTree(root):
if not root:
return None
root.left, root.right = root.right, root.left
invertTree(root.left)
invertTree(root.right)
return rootFrequently Asked Questions
What is the Invert Binary Tree problem?
Given the root of a binary tree, invert the tree and return its root. Inverting means swapping every left and right child recursively. Made famous by the "would you invert a binary tree?" meme.
How do you solve Invert Binary Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Invert Binary Tree?
Invert Binary Tree is asked at Google, Meta, Amazon, Microsoft, Apple. It is a easy difficulty problem.
What are common mistakes on Invert Binary Tree?
- Not handling the base case. If the node is `null`, return `null`. Without this, you'll get a `null` pointer exception.
- Forgetting to recurse after swapping. You need to swap children AND then invert both subtrees.
- Confusing "invert" with "mirror image." Inverting a binary tree means every left child becomes right and vice versa. The result is a mirror image.
- Not handling a single node. A single node tree is already inverted — just return it.
- Trying to invert by traversing and building a new tree. The problem says to invert in-place by swapping children. Don't create new nodes — just swap existing left and right pointers.