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.
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
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.