Invert Binary Tree

Easy#226tree nodes

You get the root of a binary tree. Turn it into its mirror image: at every node, the left and right children trade places, and return the root. Our tree: 6 with children 2 and 9; 2 has children 1 and 4, 9 has only a right child 8 — the answer: 6 with children 9 and 2; 9 now has only a left child 8, and 2 has children 4 and 1.

226 Invert Binary TreeWalkthrough · 1×

Example: mirror a binary tree: each call mirrors both subtrees first, then swaps its two children.

nonenonenonenonenonenonenone629148in order124698call stacktop on the right6
not visited yetwaiting on the call stackcurrent call, and the two arrows it swapsmirrored: children swappednone: an empty child

6 is a node, not none

01/56
restart · back · play · step
Speed
1function invert(node):
2 if node is none:
3 return none
4 left = invert(node.left)
5 right = invert(node.right)
6 node.left, node.right = right, left
7 return node
state
node
6
left
–
right
–
click a step to go back

← → step · space play/pause

Why it works

  1. The mirror of a tree is its root with the mirror of the right subtree on the left and the mirror of the left subtree on the right, so each call only needs its children's answers and one swap.
  2. A swap moves whole subtrees: when the root swaps, 2 moves right with 4 and 1, which were swapped earlier, so no node is ever swapped twice.
  3. Every node swaps its children exactly once, empty ones included, so nothing is left unmirrored.

Complexity

Time O(n): each node is visited once and does one swap. Memory O(h), where h is the height of the tree: the call stack holds one path.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.