Invert Binary Tree

Produce the mirror image of a binary tree: every node's left and right subtrees swap places, all the way down.

root = [4, 2, 7, 1, 3, 6, 9]step 1/12

Mirroring the tree is one local move — swap a node's children — repeated everywhere.

1def invert_tree(root):
2    if root is None:
3        return None
4    root.left, root.right = root.right, root.left
5    invert_tree(root.left)
6    invert_tree(root.right)
7    return root

Read the 12 steps as text

1Mirroring the tree is one local move — swap a node's children — repeated everywhere.
2At 4. Swap its two subtrees.
3Swapped — everything below 4 slides across. Now mirror each subtree the same way.
4At 7. Swap its two subtrees.
5Swapped — everything below 7 slides across. Now mirror each subtree the same way.
69 is a leaf. Already its own mirror.
76 is a leaf. Already its own mirror.
8At 2. Swap its two subtrees.
9Swapped — everything below 2 slides across. Now mirror each subtree the same way.
103 is a leaf. Already its own mirror.
111 is a leaf. Already its own mirror.
12Done. Read level by level, the tree is now [4, 7, 2, 9, 6, 3, 1].

The idea

Mirroring the whole tree sounds like it needs a plan. It doesn't — it's one local action applied everywhere. Swap a node's two children, then mirror each of those children the same way.

That's the entire algorithm, and it's worth noticing why it terminates: each recursive call is handed a strictly smaller tree, and the empty tree is already its own mirror.

The order you do it in doesn't matter. Swap first then recurse, or recurse first then swap — both produce the same tree, because swapping a node's children and mirroring those subtrees are independent operations.

The approach

1If the node is null, there's nothing to mirror — return.
2Swap the node's left and right child pointers.
3Recurse into both children.
4Return the same root; the tree was modified in place.

Complexity

Time

O(n)

Space

O(h)

Every node is visited exactly once. The space is the recursion stack, which is the tree's height — O(log n) if it's balanced, O(n) if it's a straight line.

Code

def invert_tree(root):
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

What goes wrong

•In languages without tuple assignment, overwriting left before saving it. `root.left = root.right` then `root.right = root.left` leaves both children pointing at the same subtree. Python's simultaneous assignment hides this trap; Java does not.
•Recursing before checking for null and letting it throw on the leaves' missing children.
•Doing this iteratively with a queue is perfectly valid and worth mentioning — it swaps O(h) stack for O(w) queue, which is the better trade on a very deep tree.