Invert Binary Tree — Solution

Problem

Given the root of a binary tree, return its mirror image — every left subtree and right subtree are swapped at every level, producing a reflection of the original.

[4,2,7,1,3,6,9]

• Input: root = [4, 2, 7, 1, 3, 6, 9]
• Output: [4, 7, 2, 9, 6, 3, 1]
• Explanation: Node 4's children become 7 (left) and 2 (right), and each subtree is mirrored the same way.

Counter-example: a single node [1] is already its own mirror — inverting it returns [1] unchanged.

Intuition

The problem asks for a full reflection of the tree, not just the top level. The key insight is that inverting a tree is the same as inverting the left subtree, inverting the right subtree, then swapping them — making this a naturally recursive problem. Once you accept that definition, the solution almost writes itself.

Solution — Recursive DFS

At each node, swap its left and right children, then recursively invert both subtrees. Return the node so that the caller's pointer stays valid.

1. If root is None, return None — this is the base case for leaf children.
2. Swap root.left and root.right.
3. Recursively invert the left subtree (originally the right child).
4. Recursively invert the right subtree (originally the left child).
5. Return root so the caller can attach the inverted subtree correctly.

1class Solution:
2    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
3        if root is None:
4            return None
5
6        # Mirror this node before descending so each level is handled independently
7        root.left, root.right = root.right, root.left
8
9        self.invertTree(root.left)
10        self.invertTree(root.right)
11
12        return root  # caller must receive the (possibly new) subtree root

Time: O(n) — every node is visited exactly once.

Space: O(h) — the call stack grows to the height of the tree; O(log n) for a balanced tree, O(n) for a degenerate (skewed) tree.

Complexity Summary

Common Mistakes

• Not returning root — if you write self.invertTree(root) at the call site without using the return value, an iterative caller loses the reference; always return root so the pointer chain stays intact.
• Only swapping one level — swapping root.left and root.right without recursing produces a partially mirrored tree where only the immediate children are exchanged.
• Swapping after recursing on one child — inverting root.left before doing the swap means that subtree gets inverted twice (once by the recursive call, once by the subsequent swap at this level), scrambling the result.
• Skipping the null base case — calling invertTree on a child without first checking whether the current node is None causes a null-pointer crash on leaf children.
• Building a new tree instead of modifying in place — allocating new nodes works but adds unnecessary O(n) overhead and complexity; the problem modifies the tree in place.

Related Problems

• symmetric-tree — checks whether a tree is its own mirror using the same pairwise child-comparison pattern
• same-tree — recursive structural equality; shares the identical null-check base case
• maximum-depth-of-binary-tree — foundational post-order DFS skeleton that all recursive tree problems build on
• binary-tree-inorder-traversal — basic in-order recursion; good practice for the recursive tree traversal pattern
• lowest-common-ancestor-of-a-binary-tree — deeper recursive tree logic with the same null-guard structure