Invert Binary Tree

Swap at every node, recurse into both subtrees

time O(n)space O(h) recursion stack

A mirror image is a local operation repeated everywhere: each parent just exchanges its two child pointers. Do that swap at a node and the subtrees ride along unchanged — so the same swap has to be applied inside each subtree too. Recursion does exactly that: swap here, then invert the left subtree, then the right, and the global reflection falls out of nothing more than one swap per node.

Details

Animated on: root = [4,2,7,1,3,6,9] — invert the tree (swap the left and right children of every node) and return its root. Expected: [4,7,2,9,6,3,1].

Problem:Invert Binary TreeEasy

Pattern:Tree DFS

Swap at every node, recurse into both subtrees

step 1 / 15

Call invert(4). The goal is a mirror image: every node's left and right children change places, so the job at each node is one swap, then the same job on both subtrees.

Pseudocode

1FUNCTION invert(node):
2  IF node = null:
3    RETURN null
4  SWAP node.left, node.right
5  invert(node.left)
6  invert(node.right)
7  RETURN node

← / → step · space play · Home restart

Every step in words

Show all 15 steps

Call invert(4). The goal is a mirror image: every node's left and right children change places, so the job at each node is one swap, then the same job on both subtrees.
At 4: swap its children, so 2 moves to the right and 7 to the left. The subtrees rode along with the pointers still un-inverted, so next recurse into the new left child, 7, while invert(4) waits on the stack.
At 7: swap its children, so 6 moves to the right and 9 to the left. The subtrees rode along with the pointers still un-inverted, so next recurse into the new left child, 9, while invert(7) waits on the stack.
9 is a leaf: swapping two null children changes nothing, and both invert(null) calls hit the base case immediately. This frame returns straight away.
Left subtree of 7 is done. Recurse into its new right child, 6, which still holds the original left subtree, not yet mirrored.
6 is a leaf: swapping two null children changes nothing, and both invert(null) calls hit the base case immediately. This frame returns straight away.
Both subtrees under 7 are mirrored, so invert(7) returns the node and pops. Its children now read 9 on the left and 6 on the right.
Left subtree of 4 is done. Recurse into its new right child, 2, which still holds the original left subtree, not yet mirrored.
At 2: swap its children, so 1 moves to the right and 3 to the left. The subtrees rode along with the pointers still un-inverted, so next recurse into the new left child, 3, while invert(2) waits on the stack.
3 is a leaf: swapping two null children changes nothing, and both invert(null) calls hit the base case immediately. This frame returns straight away.
Left subtree of 2 is done. Recurse into its new right child, 1, which still holds the original left subtree, not yet mirrored.
1 is a leaf: swapping two null children changes nothing, and both invert(null) calls hit the base case immediately. This frame returns straight away.
Both subtrees under 2 are mirrored, so invert(2) returns the node and pops. Its children now read 3 on the left and 1 on the right.
Both subtrees under 4 are mirrored, so invert(4) returns the node and pops. Its children now read 7 on the left and 2 on the right.
Done: level order is now [4, 7, 2, 9, 6, 3, 1]. Every node was swapped exactly once, so the whole tree costs O(n) time and the recursion never goes deeper than the tree's height.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Invert Binary Tree in the editor All Binary Trees problems Back to roadmap