Invert Tree Solution

Recursively invert subtrees, then swap:

function invertTree(root):
    if root == null:
        return null
    left = invertTree(root.left)
    right = invertTree(root.right)
    root.left = right
    root.right = left
    return root

Or swap first, then recurse. Both work:

function invertTree(root):
    if root == null:
        return null
    temp = root.left
    root.left = root.right
    root.right = temp
    invertTree(root.left)
    invertTree(root.right)
    return root

Time: $O(n)$. Space: $O(h)$.

The order doesn't matter because swapping at one level is independent of swapping at other levels.