## Saturday, March 7, 2020

### Problem Statement

Invert a binary tree.
Example:
Input:
```     4
/   \
2     7
/ \   / \
1   3 6   9```
Output:
```     4
/   \
7     2
/ \   / \
9   6 3   1```
Trivia:
This problem was inspired by this original tweet by Max Howell:
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.

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

Simple question on understanding about recursion. It could be solved using pre-order and post-order traversal style recursion. It can also be solved iteratively using a queue. Please refer to Leetcode official solution. It's very similar to "Binary Tree ZigZag Level Order Traversal". Remember a full binary tree max leaf is (N+1)/2 or ceiling of N/2
, that's the O(N) space complexity using a queue.

If you are like Max Howell, you can show off but I would still recommend to stay humble if you really want the job. Brillient jerks are rare (IMHO Linus Torvalds is one) but very productive, but not all companies would accept those culture (Netflix does but not others). Be strong and humble.

### Solutions

#### Recursion (pre-order and post-order)

Time Complexity: O(N), where N is the total number of tree nodes
Space Complexity: O(1) Or O(lgN) if you count the recursion function stack

### References

#### 1 comment:

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!