Invert Binary Tree

Signal

"Apply the same transform to every node" is the canonical single-pass recursive shape — when a problem reshapes a tree uniformly, recurse on the children and let the return value assemble the answer; you never need to reason about the whole tree at once.

Approach

Recursively invert the left and right subtrees, then swap the (already inverted) results into node.left/node.right. An empty node inverts to itself (None).

Skeleton

def invert(node):
    if not node: return None
    node.left, node.right = invert(node.right), invert(node.left)
    return node

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def invert_tree(root: TreeNode | None) -> TreeNode | None:
    if root is None:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

Complexity

O(n) time — every node visited once. O(h) recursion stack space, where h is tree height (O(n) worst case on a skewed tree, O(log n) balanced).

Pitfalls

• Assigning sequentially (node.left = invert(node.right) then node.right = invert(node.left)) reads node.left after it was already overwritten — Python's simultaneous tuple assignment evaluates both sides of = before assigning either, which is what makes the one-liner safe.
• Forgetting the recursion needs to happen on the ORIGINAL children before any swap — invert bottom-up, not top-down.