June LeetCoding Challenge, 1st Day, Invert Binary tree

Introduction

This is the first day of June, LeetCoding challenge and the first problem is to invert a binary tree. There was a very popular tweet by Max Howell, when google rejected him in an interview.

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

Approach

By looking at the picture above you can clearly see what is the input and what is the output. The common mistake that one can do is to think that just change left child to right and right child to left and we are done. However this is not the case. The left child must also be inverted and the right child should also be inverted.

So what we can do is to invert the left and set it as the right child, then invert the right and set it as the left child and then we will be done in reality.

Here is the accepted Python solution

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root == None:
            return None
        else:
            left = self.invertTree(root.left)
            right = self.invertTree(root.right)
            root.left = right
            root.right =left
            return root

Discussion

What will be the complexity of this solution ? Well, we are traversing each node only once, so the complexity would be Big O of number of nodes in the tree. Recursive solutions to Tree problems are seemingly easily to comprehend. Can you try iterative solution ? Post in the comments, But before that, submit it on leetcode below link and check if it is accepted or not.

https://leetcode.com/explore/challenge/card/june-leetcoding-challenge/539/week-1-june-1st-june-7th/3347/