Mirrors swap left and right. This means to solve the problem, all we have to do is swap every node's left and right pointers, like this:

We want to write a function that swaps every node's left and right pointers.

1. Recursion

To create a recursion, you can first swap the left and right pointers of the current node. Afterwards, you can invert the remaining left and right trees. Here's the recursion. The same way that 1 + 1 = 2, here's what the recursion is equal to:

2. Base case

The recursion calls itself on lower and lower nodes in the tree until it eventually gets to a node that's null. This is where the recursion breaks, since invertAll(None) will use None.left and None.right - this gives an error. We can't use the recursion to get what invertAll is equal to in this case, so we need to manually find what it's equal to. It's pretty obvious that inverting a null node is the same as doing nothing.

3. Code

To code the solution, we can write a function that always does whatever invertAll is equal to. This way it's guaranteed to be correct. It's always equal to the recursion, unless we're in the base case where it's equal to doing nothing.

Time Complexity $O(n)$. We visit all $n$ nodes, which takes $O(n)$ time. And we swap their left and right pointers which takes $O(1)$ time. This is a total of $n \cdot O(1) = O(n)$ time.

Space Complexity $O(n)$. For now, you don't need to know where this comes from - we'll go over the full details in the next lesson "Call Stack". Just know the computer needs some memory to keep track of the function calls it's making.