The problem
Given a binary tree, invert it: swap every node’s left and right child, producing its mirror image.
Input: [4, 2, 7, 1, 3, 6, 9] Output: [4, 7, 2, 9, 6, 3, 1]
Picture it
Picture a hanging mobile. Every hook (a node) has a left arm and a right arm. Holding the mobile up to a mirror means swapping the arms at every hook. We visit each hook, swap its two arms, then do the same for the hooks below.
How to recognise it
- The input is a binary tree and the output is the same tree, changed in place.
- The change is local: every node does the same small job (swap its two children) and needs nothing from its parent.
- "Mirror", "flip" or "swap left and right" at every level is the classic wording.
- Only up to 100 nodes, so any approach that touches each node once is enough. The point of the problem is the recursive shape, not speed.
Start with brute force
There is no slow brute force here, because every correct approach must visit every node. The naive version builds a brand-new mirrored copy and returns it, leaving the original untouched.
def mirror_copy(node):
if not node:
return None
return Node(node.val, mirror_copy(node.right), mirror_copy(node.left))
It is O(n) time, which is already optimal, but it allocates n new nodes: O(n) extra memory on top of the O(h) recursion stack (h is the tree height). With 100 nodes that costs nothing, but the in-place version shows the pattern you will reuse on bigger trees.
From brute force to the idea
- Find the waste. The copy creates a new node for every old one, only to throw the old tree away. The old nodes already have the right values.
- Ask what one node must do. At a single node, the mirrored tree has the old right subtree on the left and the old left subtree on the right, each mirrored. So: mirror both children, then swap the two pointers.
- Trust the recursion.
invert_tree(node.left)andinvert_tree(node.right)fix everything below; the tuple assignmentnode.left, node.right = node.right, node.leftswaps them in one step, with no temporary variable. - Stop at empty spots. An empty child returns
Noneand has nothing to swap.
This is the key idea: mirroring a tree means swapping the children at every node, and a depth-first search (DFS: follow one branch to the bottom before trying the next) visits each node once.
The shown code inverts the children first and swaps afterwards (post-order). Swapping first and then recursing (pre-order) works equally well: every node gets swapped exactly once either way.
The key idea
Recursion: invert the left subtree, invert the right subtree, swap them. Every node is visited once: O(n).
Python solution
def invert_tree(node):
if not node:
return None
invert_tree(node.left)
invert_tree(node.right)
node.left, node.right = node.right, node.left # swing the two arms
return nodeIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (mirrored copy) | O(n): one new node per old node | O(n): n new nodes, plus O(h) recursion stack |
| In-place swap (shown code) | O(n): each node is visited and swapped once | O(h): one stack frame per level, h = n for a chain |
Edge cases
- Empty tree (
None): returnsNone. - Single node: returned unchanged.
- Chain
[1, 2, null, 3](each node has only a left child): becomes a right-leaning chain[1, null, 2, null, 3]. - Inverting twice gives back the original tree, a quick self-test.
- Very deep tree: about 1,000 levels hits Python's default recursion limit. LeetCode caps this problem at 100 nodes, so it cannot happen here.
Common mistakes
- Writing
node.left = invert_tree(node.right)and thennode.right = invert_tree(node.left): the second line reads the left child that was just overwritten. - Forgetting
return nodeat the end, so the caller receivesNoneinstead of the root. - Swapping only the root's children and not recursing, which mirrors one level only.
Decide whether a binary tree is a mirror image of itself (LeetCode 101): [1, 2, 2, 3, 4, 4, 3] is symmetric, [1, 2, 2, null, 3, null, 3] is not. Do it without changing the tree. Describe your approach, then write it if you like.
Compare with our answer
Compare the tree with its own mirror without building it. Walk two pointers at once: when one goes left, the other goes right. Two spots match if both are empty, or both hold the same value and their outer and inner children match.
def is_symmetric(root):
def mirror(a, b):
if not a or not b:
return a is b # both empty?
return (a.val == b.val
and mirror(a.left, b.right)
and mirror(a.right, b.left))
return mirror(root, root)
Time O(n), space O(h). An empty tree counts as symmetric.
A strong answer mentions: pairing left with right (outer with outer, inner with inner), the both-empty base case, and that it reads the tree without modifying it.
1. You must check whether two binary trees are mirror images of each other. Which approach fits best?
A paired DFS compares mirrored positions directly in O(n) without changing either tree. Level or in-order lists lose the shape, so different trees can produce the same lists, and inverting both trees just compares them as they are.
2. Why does the shown solution need only O(h) extra space?
No new nodes are made, and a DFS keeps one frame per level of the current path, so the height h decides the space. Python has no tail-call optimisation, so frames are not reused.
3. A learner writes node.left = invert_tree(node.right) then node.right = invert_tree(node.left). Which tree still comes out right?
The second line reads node.left after it was overwritten, so the old left subtree is lost and the new left subtree is used twice. [2, 1, 3] becomes [2, 3, 3]. Only a node with no children has nothing to lose.
Score 60% or more and the lesson is marked complete.