LeetCode 226 Invert Binary Tree - Algorithm

The algorithm is three steps:

$1.$ If the node is null, return null (base case).

$2.$ Swap the left and right children of the current node.

$3.$ Recursively invert the left subtree and the right subtree.

You can swap before or after the recursive calls. The order does not matter because you are processing the whole tree. The recursion ensures every node gets its children swapped. This is a post-order traversal in disguise. You process children first (by recursing), then handle the current node (by swapping).

This runs in $O(n)$ time and uses $O(h)$ space.