Pattern visualizer

Invert Binary Tree

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. 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]..

Swap at every node, recurse into both subtrees

time O(n)space O(h) recursion stackstep 1 / 15

line 1

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap