Given the root of a binary tree, invert it — swap every left and right child — and return the new root.
Example
Input root = [4,2,7,1,3,6,9]
Output [4,7,2,9,6,3,1]
Key Pointers
Inverting is just swapping left/right at every node — a mirror image, not a value reorder.
Recursion handles this naturally: invert the subtrees first, then swap the results.
An iterative version with a queue or stack works the same way if recursion depth is a concern.
Step-by-Step Analysis
Base case: if root is None, return None.
Recursively invert the left subtree and the right subtree.
Swap root.left and root.right using the inverted results.
Return root.
Complexity
Time: O(n) — Space: O(h) recursion stack, where h is the tree's height
Code
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root: TreeNode | None) -> TreeNode | None:
if not root:
return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root
Code Explanation
How the solution above works, piece by piece.
Base case: an empty subtree inverts to an empty subtree.
invertTree(root.right) and invertTree(root.left) first mirror each child subtree completely.
The tuple assignment then stores the (already inverted) right subtree as the new left and vice versa. Both calls run before either field is overwritten, so nothing is lost.
Return root so the parent can link it back in.
Each node is visited once: O(n) time, O(height) recursion stack.
Visual Walkthrough
Running it on root = [4, 2, 7, 1, 3, 6, 9]:
Every node swaps its left and right child, at every level, so the whole tree becomes its mirror image. The colours follow the subtrees rooted at 2 and 7 to the other side.