[Solution]Problem 59:Invert Binary Tree [Google]

Recursion, Trees

Oct 07, 2022

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

Take the next step by subscribing here

We’re going back to a classic

I like this problem because it’s great for demonstrating a lot of the fundamentals that you will need to solve harder problems involving recursion, trees, graphs, and dynamic programming.

This problem can be found as problem 226. Invert Binary Tree

Problem

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

You can test your solution here

Step 1: Understanding the Problem

All great solutions come from understanding the problem you’re trying to solve. Thus, it is important to really understand what the question expects you to do. This will help you understand how to do it.

In our case, we want to invert the binary tree nodes. What exactly does this mean? Looking at our cases, we’re swapping the left and right nodes for a parent node. The code for it would like

root.left,root.right= root.right, root.left

This is not too hard, but when modifying nodes in binary trees it’s good to add an extra layer of caution. This is because any changes you make will affect both the nodes you have and the children of the nodes. You don’t want to ignore potential downstream effects your code might have. So let’s see what this will do to the children and if those outcomes are acceptable.

Step 2: Understanding the outcomes

In our current solution, we are swapping the nodes with common parents, on the same level. This is pretty neat because in a way it localizes the effects of our swapping. It also lines up very well with what we want to do for our solution (notice that in our code, we’re doing the same thing). So there’s no issues with that. So far this means we can follow the approach of-

root.left,root.right=root.right, root.left
invert(root.left)
invert(root.right)

This will run layer by layer and swap the children of a node. Obviously, in your code you want to account for the base cases. I’ll let you fill that in.

As a sanity let’s run the algorithm we have with the input we have been given. You will see that this approach checks out. Yipee!

However, this is where a lot of people trip up with recursive solutions. Especially when it comes to the harder problems. They freeze up, because they aren’t sure if the solution will scale up to the larger input cases. What about some super funky variant, that you haven’t though of yet? How much testing is enough?

If you’re someone struggling with this, I want you read the following post on the Recursive Leap of Faith. This technique is something that you want to integrate into your very soul. Tl;dr- Once you have built out a solution to account for edge cases and the recursive conditions (and tested this solution on small inputs), just assume it works for the larger cases. Details on it, and why this works are in the post below.

Technology Made Simple

Recursive Leap of Faith [Technique Tuesdays]

Cama-ihi my amazing reader, That’s one of the common traditional Alaskan ways of saying hello (good to see you). As this newsletter and my articles have grown more, I have been able to interact with a lot more of you. This is more validation of the effectiveness of the approach I have been pushing…

3 years ago · 2 likes · Devansh

So we will take a leap of faith and say that our algorithm works. Neat. Now let’s get to coding things up. However, before I give you the full Leetcode Python code, I want to show you another technique that you should have in your tool-kit. It is unneccesary for this problem, but when you come across much tougher recursion problems.

Step 3: Using a Helper Function

If you’ve spent any meaningful period of time looking through Leetcode solutions, you will know that people occasionally helper functions for recursive problems. But noone tells you why. Well once again, your favorite Tech Cult Leader has your back.

Remember how we talked about localizing the effects of your functions. You always want the changes your code makes to affect as small an ‘area’ as possible. This is the basics of code design, and helps in every area from optimization, code modification to debugging. If your code is changing more than it absolutely needs to, it can lead to all kinds of messes.

With recursion…the messes you can create are on steroids. All kinds of depenencies and memory overflows become possible. Thus, this principle is even more important when using recursion.

Helper functions are one way to avoid this. By containing all the recursive parts to the helper functions, you can deal with the recursion in isolation. This is life-changing and make both your code design and testing soo much better. Recursive functions also tend to follow a lot of patterns, so by isolating them into one area, you can really make things easier on yourself. Take the Word Search problem, which I covered here. By isolating the dfs in one area, we can actually sketch our that part of our solution pretty quicky, since we just have to apply the standard recursive formula-

Check for termination cases. Done by checking whether we’ve hit the word, gone to a previously visited tile, or gone out of bounds. For our invert problem this happens when root is null.
Do the processing- In this case it’s, it’s marking a cell as visited. For invert- it is swapping the children.
Move on to the recursive case- Self Explanatory.

Since this is a backtracking problem, we reset our state after recursion. But everything else is the same.

For more details about that problem, check out that solution. The important point is that I want you to see how a helper function can make your life when coding recursion much much easier. Drill that habit into your self, and you will reap the rewards. With that in mind, take a look at the code.

Step 4: Coding it up

With all this covered, the code is not difficult to write up.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def invertHelper(root):
            if(not root):
                return []
            root.left,root.right=root.right, root.left
            invertHelper(root.left)
            invertHelper(root.right)
        invertHelper(root)
        return root

Again, make sure you really understand the leap of faith and the use of helper functions. Both will be game changing for your interview prep going forward.

Time Complexity- O(N). We visit every node.

Space Complexity- O(N). We have to create a stackframe. In practice, machines are optimized to make it much more efficient.

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.