Invert Binary Tree

def invertTree(node):
    if node is None:
        return None
    node.left, node.right = node.right, node.left  # swap
    invertTree(node.left)
    invertTree(node.right)
    return node

Invert Binary Tree. Given the root of a binary tree, turn it into its mirror image: at every node, the left and right children trade places. Return the root.

Here's our tree: four at the top, two and seven below it, then one, three, six and nine. Hold it up to a mirror, and it reads four; seven, two; nine, six, three, one.

Swapping only the top isn't enough. Seven and two trade sides, but their children come along unflipped, so the bottom row is still backwards.

The fix is recursion. To invert a node, swap its two children, then invert each child the same way. An empty spot is the base case: there's nothing to do.

In code: if the node is None, return None. Swap left and right in one line. Invert the left, invert the right, and return the node.

Let's run it. Invert four: swap, so seven moves left and two moves right. Step into seven: swap, and nine and six trade places. Nine and six are leaves, so their calls just return. Back to four, then into two: swap, and three and one trade places. Now it's the mirror.

Each node is visited once and swapped once, so the time is O of n. The call stack holds one call per level, so the extra space is O of h, the tree's height.

Swap the children; recursion does the rest. That's Invert Binary Tree.