Invert Binary Tree (LeetCode 226)

The problem

You get the root of a binary tree. Invert it, meaning produce its mirror image, where every node’s left and right children are swapped. Return the root.

Input:                Output:
        4                     4
      /   \                 /   \
     2     7               7     2
    / \   / \             / \   / \
   1   3 6   9           9   6 3   1

Level order: [4,2,7,1,3,6,9]  ->  [4,7,2,9,6,3,1]

Every level reads right-to-left after the inversion.

How to think about it

Start with brute force. You might think level by level: read each level, reverse it, and rebuild the tree. That needs extra storage, and rebuilding the links correctly is fiddly. It also misses how simple the real structure is.

The key insight: mirroring a tree means mirroring each subtree and then swapping them. If you invert the right subtree and hang it on the left, and invert the left subtree and hang it on the right, the whole tree is mirrored. So at every node, swap the two (already inverted) children. That’s it.

The order doesn’t matter much. You can swap first and then recurse (preorder), or recurse first and swap on the way back up (postorder). Both touch every node once. Python’s tuple assignment lets you do the recursion and the swap in one line, because the right-hand side is fully evaluated before either assignment happens.

Which pattern is this? Tree DFS. The tell is “do the same thing to every node, and the result for a tree is built from the results for its subtrees”.

Approach

1. If the node is empty, return None.
2. Invert the right subtree and the left subtree recursively.
3. Attach the inverted right subtree as the new left child, and the inverted left as the new right.
4. Return the node.

Solution

def invert_tree(root):
    if not root: return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)   # RHS evaluated first, then swapped in
    return root
# invert(tree[4,2,7,1,3,6,9]) level-order -> [[4],[7,2],[9,6,3,1]]

Dry run

On the example. Each node finishes after both its subtrees, so this is the order the swaps complete in:

Reading the result level by level gives [[4], [7, 2], [9, 6, 3, 1]].

Complexity

• Time: O(n). Every node is visited once and does one swap.
• Space: O(h). The recursion stack goes as deep as the tree height h: O(log n) balanced, O(n) skewed. The tree is changed in place, so no other memory is used.

Edge cases and pitfalls

• Empty tree returns None.
• Single node returns itself unchanged.
• Swapping in two lines without a temp is a classic bug: root.left = invert(root.right) followed by root.right = invert(root.left) inverts the new left, which is the old right, twice. Use tuple assignment or a temporary variable.
• Deep trees can exceed Python’s recursion limit. A BFS with a queue that swaps children at each node works just as well.

Related problems

• Same Tree (LeetCode 100): the same two-subtree recursion, returning a boolean.
• Maximum Depth of Binary Tree (LeetCode 104): the simplest recurse-combine-return example.
• Binary Tree Level Order Traversal (LeetCode 102): the BFS you’d use to print and check the inverted tree.