Invert a binary tree.
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.
I was not able to solve this problem at the begining. I felt myself so stupid after seeing the DFS approach for just 5 lines. After two weeks from previous submission. I was able to recall all three different approaches.
Recursive DFS is acutally very straight forward. For each node, swap its left & right child. Recursively call
invertTree(left) to the rest of the tree.
// recursive dfs, top-down, might cause stack overflow
The above approach recursive dfs use top-down approach, where swap is performed along the way from top to bottom. The bottom-up approach is also possible.
// recurive dfs, bottom-up, might cause stack overflow
The bottom-up approach first go down to the far left node in the left subtree. Then swap start from there and its right subtree and return
node to upper level. The process is very similiar to pre-order traversal.
Both recursive dfs approach might cause stack overflow if tree is extremely unbalanced, hence the height of tree might be large to cause stack overflow. Let’s take a look at the iterative approach with
Stack data structure.
// iterative dfs no stack overflow
As we can see, iteative dfs, indeed, is very similiar to recursive top-down approach. The recursive top-down approach uses an implicit
Stack and iterative dfs uses an explicit
Benefit from the nature of this problem, we can also use BFS to solve it.
// BFS, change stack to queue
BFS approach uses level order traversal to push node and swap them in order. The overall strcture is very similiar to the iterative dfs version.
- DFS recurisve (top-down)
- DFS recurisve (bottom-up, preorder traversal)
- DFS iterative (stack)
- BFS iterative (queue, level-order traversal)
- 02/03/2019 Add solutions