DSA problem
Invert Binary Tree
Given the root of a binary tree, invert the tree by swapping the left and right child of every node, and return its root. The shape of the resulting tree is the mirror image of the original — every node still holds the same value, but the entire left subtree and right subtree of every internal node have been exchanged.
The intuition is delightfully simple once you frame it as a recursion. To mirror the whole tree, you must mirror the left subtree, mirror the right subtree, and then swap which one hangs off the current root. Because the children are themselves trees, the recursion bottoms out at null, which mirrors to itself trivially.
It is most naturally expressed as a post-order traversal: descend into both children first, fully invert each, and only then swap the pointers at the current node. Doing the swap before recursing also works (a pre-order shape) because we only relabel pointers, not values, but post-order is the textbook framing that generalizes to problems where the swap must depend on already-computed subtree results.
The solution runs in O(n) time, visiting each node exactly once and performing a constant-time swap, and consumes O(h) call-stack space where h is the height of the tree. For a balanced tree that is O(log n); for a skewed tree it degrades to O(n).
Examples
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]root = [2,1,3][2,3,1]root = [][]Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
- The tree is a valid binary tree.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.