LC 226 · Easy · Post-order · same walk, different work
Invert Binary Tree
The tree is being restructured, and the change at each node is local and identical.
Recognise it
Before any code, what in the question tells you this is the pattern?
You are asked to restructure a tree rather than measure it. The tell is that the change at each node is local and identical, which means the recursion is the same as any other traversal and only the body changes.
The brute force
Always have this one ready. It is the honest starting point, and it is what the real solution improves on.
Read the tree into a level-order array, reverse each level, and rebuild the tree from the array.
O(n) time and O(n) extra space.
It gets the right answer and is much harder to write correctly than the real solution. The rebuild step is where it goes wrong, because a level with holes in it does not reverse the way the array suggests. When a transformation is purely local, going via a global representation is a detour that adds the only hard part.
The approach
The idea in plain language, before it becomes syntax.
Mirroring a tree means swapping the two children of every node. There is no ordering to maintain and no information to gather, so this is the same walk as measuring depth with a different line in the middle.
The one real hazard is the order of operations. If you assign the new left child before reading the old one, you have destroyed the subtree you still need. Python hides this because tuple assignment evaluates the whole right side first. In JavaScript and Java you have to hold both results in temporaries, and an interviewer will look for exactly that.
Returning the node rather than mutating silently is what lets the recursive calls sit directly in the assignment. It also makes the function composable, which matters when a follow-up asks you to invert a subtree in place.
The algorithm
The same idea again, as steps you could follow with a pencil.
The solution
Now the code, and why each decision in it is the way it is.
def invertTree(root):
if not root:
return None
# The right side is evaluated first, so neither child is lost.
root.left, root.right = invertTree(root.right), invertTree(root.left)
return rootEvery node is visited once and does constant work, so this is linear time and stack-height space, the same as every other single-pass tree walk.
Pre-order and post-order both work here. Swapping before or after recursing gives the same result, because the swap at a node does not depend on what happened below it. That is not true for most tree problems, so it is worth noticing why it is true for this one.
The empty case returns null rather than raising. That keeps the caller free of null checks, which is the whole reason the base case is the null node and not the leaf.
Where people slip
- Compute both recursive results before assigning. Writing
root.left = invert(root.right)first destroysroot.left, so the second call inverts the subtree you just wrote. - Python tuple assignment sidesteps this because the right side is evaluated first. In Java and JavaScript you need explicit temporaries, which is exactly the kind of detail interviewers watch for.
- Returning the node is what makes the one-line assignment style possible. A version that mutates without returning forces a clumsier caller.
Your notes
What tripped you up here? Write it in your own words.