Invert Tree

Given the root node of a binary tree root, turn the tree into its mirror image. This is also called "inverting" the tree.

You should modify the tree in-place, and should not return anything.


First Few Test Cases:

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)O(n). We visit all nn nodes, which takes O(n)O(n) time. And we swap their left and right pointers which takes O(1)O(1) time. This is a total of nO(1)=O(n)n \cdot O(1) = O(n) time.

Space Complexity O(n)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.

Mark as Completed:
Test your code to get an output here!
Test your code to get an output here!