## Description

Invert a binary tree.

Input:

1 | 4 |

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

## Thoughts

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 (Top-down)

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.

1 | // recursive dfs, top-down, might cause stack overflow |

### Recursive DFS (Bottom-up)

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.

1 | // 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**.

### Iterative DFS

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.

1 | // 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** `Stack`

.

### Iterative BFS

Benefit from the nature of this problem, we can also use BFS to solve it.

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

## Summary:

- DFS recurisve (top-down)
- DFS recurisve (bottom-up, preorder traversal)
- DFS iterative (stack)
- BFS iterative (queue, level-order traversal)

## Logs

- 02/03/2019 Add solutions