{ }SolveLogs
⌕
Home / Binary Trees / #226
LeetCode #226 Easy

Invert Binary Tree

Invert Binary Tree is LeetCode 226 (Easy). You get the root of a binary tree and must turn it into its mirror image: at every node, the left child and the right child trade places. Return the root of the mirrored tree.

  • The tree has at most 100 nodes and may be empty.
  • Change the tree in place; no new nodes are needed.
Constraints
  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
treedfsrecursion
Open on LeetCode ↗
02

Intuition

Mirroring a whole tree sounds like a big job, but it is one small move repeated at every node. Invert binary tree comes down to this: swap the two children of each node.

Look at the root first. After its swap, the old right subtree sits on the left and the old left subtree on the right. Each of those subtrees still has its own left and right the old way round, so each needs mirroring too, which is the same problem on a smaller tree. That is why recursion fits: swap here, then invert both children.

Every node is swapped exactly once, so the work is O(n).

How to spot this pattern

"Do the same thing to every node" is the shape of this problem: handle the node, then recurse into both children. Symmetric Tree (101) asks whether a tree equals its own mirror, and Same Tree (100) walks two trees side by side the same way. The invert binary tree LeetCode problem is often the first tree recursion people write.

03

Approach

Try it first

Before reading on, mirror [4,2,7,1,3,6,9] on paper. Then decide: does it matter whether a node's children are swapped before or after the subtrees below them are inverted?

Two ways to solve it

RecursiveBest
Time O(n)Space O(h)

Swap the current node's children, then call the same function on each child.

  • Space: one call per level of the tree.
  • Code: four short lines.
  • Limit: a very deep chain could hit the recursion limit.

The standard answer for LeetCode 226.

Solution & demo ↓
Iterative BFS (queue)
Time O(n)Space O(n)

Take nodes off a queue level by level, swap each one's children, and queue the children.

  • Space: the queue holds a whole level, up to about n / 2 nodes.
  • Depth: no recursion, so no stack limit.
  • Order: top to bottom, one level at a time.

Handy when the tree may be very deep.

Code ↓

Both swap every node once in O(n) time, but on a balanced tree the recursion keeps only one path in memory, and its code is shorter. The steps, code and live demo below follow the recursive version; the queue code comes after the demo.

1

Stop at an empty node

If root is empty, return it as it is. An empty tree is already its own mirror. This base case ends every branch of the recursion, so a leaf needs no special code: its two missing children are just two calls that return at once.

2

Swap the two children

Exchange root.left and root.right in one move. In the invert binary tree Python code that is a tuple assignment; C++ uses swap and Java a temporary variable. Both pointers are read before either is overwritten, so neither subtree is lost.

3

Invert both subtrees, then return

Call the function on root.left and on root.right. They now hold each other's old subtrees, and each call mirrors its own subtree down to the leaves. Finally return root: the tree was changed in place, so the root is the same node.

04

Invert Binary Tree solution in Python | C++ | Java

▶1class Solution:
▶2 def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
▶3 if not root:
▶4 return None
▶5 root.left, root.right = root.right, root.left
▶6 self.invertTree(root.left)
▶7 self.invertTree(root.right)
▶8 return root
this callswapped4271369calls4topcall invert(4)
root4not empty
Start at the root. The root is not empty, so the base case does not apply. The plan for every node is the same: swap its two children, then invert each child.
this callswapped4271369calls4topswap at 4: left 2 ↔ right 7
node4
left7was 2
right2was 7
Swap at 4. Both child pointers are read before either is written, so neither subtree is lost. The whole 2 subtree and the whole 7 subtree trade sides, but their insides are not mirrored yet.
this callswapped4271369calls47topswap at 7: left 6 ↔ right 9
node7
left9was 6
right6was 9
Swap at 7. Its children 6 and 9 trade sides. Next the call goes into the new left child, 9, and mirrors it before the right one.
this callswapped4271369calls479topleaf 9: both children empty → return
node9a leaf
childrenempty, emptybase case twice
9 is a leaf. Swapping two empty children changes nothing, and both recursive calls land on an empty node and return at once. So 9 is finished and goes back to its parent.
this callswapped4271369calls476topleaf 6: both children empty → return
node6a leaf
childrenempty, emptybase case twice
6 is a leaf. Swapping two empty children changes nothing, and both recursive calls land on an empty node and return at once. So 6 is finished and goes back to its parent.
this callswapped4271369calls47top7 done → return to 4
node7both subtrees mirrored
Both calls under 7 have returned, so its whole subtree is mirrored. Return 7 to its parent, which can move on to its other child.
this callswapped4271369calls42topswap at 2: left 1 ↔ right 3
node2
left3was 1
right1was 3
Swap at 2. Its children 1 and 3 trade sides. Next the call goes into the new left child, 3, and mirrors it before the right one.
this callswapped4271369calls423topleaf 3: both children empty → return
node3a leaf
childrenempty, emptybase case twice
3 is a leaf. Swapping two empty children changes nothing, and both recursive calls land on an empty node and return at once. So 3 is finished and goes back to its parent.
this callswapped4271369calls421topleaf 1: both children empty → return
node1a leaf
childrenempty, emptybase case twice
1 is a leaf. Swapping two empty children changes nothing, and both recursive calls land on an empty node and return at once. So 1 is finished and goes back to its parent.
this callswapped4271369calls42top2 done → return to 4
node2both subtrees mirrored
Both calls under 2 have returned, so its whole subtree is mirrored. Return 2 to its parent, which can move on to its other child.
this callswapped4271369callsnonereturn root → [4,7,2,9,6,3,1]
return[4,7,2,9,6,3,1]level order
work7 swapsone per node, O(n)
Done. Every node had its children swapped exactly once, so every left-right order in the tree is reversed. The root is the same node, so it is returned as the answer.
05

Iterative BFS (queue)

The queue starts with the root. Each node taken off the queue has its two children swapped, and the children that exist join the queue, so every node is swapped once, level by level.

▶1class Solution:
▶2 def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
▶3 queue = deque([root] if root else [])
▶4 while queue:
▶5 node = queue.popleft()
▶6 node.left, node.right = node.right, node.left
▶7 if node.left:
▶8 queue.append(node.left)
▶9 if node.right:
▶10 queue.append(node.right)
▶11 return root
06

Common pitfalls

Assigning the children one line at a time

✗ Wrong
root.left = self.invertTree(root.right)
root.right = self.invertTree(root.left)
✓ Right
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)

The first line overwrites root.left before the second line reads it. The second call then inverts the old right subtree a second time and puts it on both sides, and the old left subtree is lost.

Forgetting to return the root

✗ Wrong
self.invertTree(root.left)
self.invertTree(root.right)
✓ Right
self.invertTree(root.left)
self.invertTree(root.right)
return root

The swaps happen in place, but LeetCode reads the tree from the returned root. Without return root, Python returns None and the answer is an empty tree.

07

Complexity

Time
O(n)
Space
O(h)
Each node is swapped once. The recursion keeps one root-to-leaf path open: O(log n) on a balanced tree, O(n) on a chain.
08

Invert Binary Tree FAQ

Can the swap go after the recursive calls?

Yes. Swapping first or swapping last both work, because each node's children are swapped exactly once. Swapping between the two calls does not: after invert(left) and the swap, root.right is the subtree that was just inverted, so it gets inverted twice and the other one never.

← Prev · #225
Implement Stack using Queue
Next · #227 →
Basic Calculator II