Given the root of a binary tree, the machine must flip the tree horizontally so every left subtree becomes the right subtree and vice versa. The task is a structural transform, not a value change: node values stay put, only the child pointers swap.
The key insight is that the transform composes. Once you have inverted the left subtree and the right subtree, inverting the current node is just one swap of its two children. That makes this a textbook post-order DFS: recurse down, do the work on the way back up.
The approach runs in three steps. First, if the node is null, return it immediately — this is the base case. Second, recurse on the left and right children so both subtrees are already inverted when the call returns. Third, swap the (now-inverted) children and return the node. The machine walks the whole tree once, so time is O(n) and space is O(h) for the call stack, O(log n) on a balanced tree and O(n) in the worst case of a chain.
The trickiest edge case is the empty tree: root is null, so the base case fires immediately and the machine returns null. There is nothing to swap. The same base case also protects leaf nodes, whose children are both null. Swapping a node's children is safe even when one or both are null — the machine just assigns null pointers and moves on.
def invertTree(root):
if not root:
return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root