March 24
Invert Binary Tree
How to notice that inverting a tree is just swapping left and right at each node and letting recursion handle the rest.
Trees Beginner 10 min TypeScript
Given the root of a binary tree, invert the tree and return the root.
Inverting means mirroring left and right at every node.
Example:
Input: [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
What to notice before coding
- The problem changes the structure of the tree, not the values.
- An empty tree is still valid.
- The same rule applies to every node.
Common mistakes
- swapping the children of one node and forgetting to continue recursion
- overwriting one side before preserving the other
Step 1 - Stop thinking about the whole tree at once
Many people freeze on tree problems because they try to visualize everything at the same time.
You do not need that here.
The right question is smaller:
- what has to happen at this node?
Step 2 - Find the local rule
At each node, inverting means:
- what used to be
leftbecomesright - what used to be
rightbecomesleft
That is it.
Step 3 - Write a baseline that makes the idea visible
A valid baseline is building a new mirrored tree with recursion:
- copy the value
- build the left side from the old right
- build the right side from the old left
It works and makes the recursion explicit.
Step 4 - Notice that you do not even need a new tree
If you can modify the current node, you only need to:
- invert the children
- return the same node
Recursion handles the rest.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function invertTree(root) {
// root is an object like { val: number, left: ..., right: ... } or null
// your solution here
return root
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(h)
Solution 1 - Build a new mirrored tree
Good baseline because it shows the rule without side effects.
export function invertTree(root) {
if (root === null) {
return null
}
return {
val: root.val,
left: invertTree(root.right),
right: invertTree(root.left),
}
}It works, but it creates new structure without needing to.
Solution 2 - Swap in place with recursion and implicit DFS
Now you reuse the original tree.
export function invertTree(root) {
if (root === null) {
return null
}
const left = invertTree(root.left)
const right = invertTree(root.right)
root.left = right
root.right = left
return root
}The main point is that recursion returns the children already inverted. From there, you just reconnect them.
What to say in the interview
A strong short explanation would be:
I think locally. For each node, I need to swap left and right.
Recursionsolves the children, and then I reconnect both sides at the current node. That visits each node once inO(n).
That shows that you:
- do not get lost trying to visualize the whole tree
- can turn a local rule into recursion
- understand what the function returns at each call
When this pattern shows up again
The same pattern comes back when you need to:
- apply the same rule to every node
- solve subtrees and combine at the parent
- think about trees through local recursion
- prepare for depth, traversal, BST, and LCA
The point is not memorizing
invertTree.
The point is learning to ask “what happens at this node?”.