## Saturday, October 5, 2019

### Problem Statement

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
```Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

1            <---
/   \
2     3         <---
\     \
5     4       <---```

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

This is a great problem and I highly recommend we solve it in both DFS and BFS for level order traversal because it  covers everything we need to know about trees in interviews.

This would be a better test case because right subtree would not be deep enough to cover the left subtree
```   1            <---
/   \
2     3         <---
\
5             <---```
`[1, 3, 5] `

#### Level order traversal using BFS(queue)

It should be relatively natural for us think about using level order traversal and we can simply use a queue and always find the right most element when we pop out element from each level.

#### Level order traversal using DFS(map)

A pre-order traversal way, just like order level traversal using DFS with a map(key is depth, value is node). This method utilizes a depth to value map to record the right most value on each order while performing a pre-order traversal, namely record the node value, go left then go right. This way, right value can always overwrite the left value thus keeping a “right side view”

I personally don't like the leetcode official solution, where in DFS you don’t need two stacks and in
BFS you don’t need the maps.

### Solutions

#### Level order traversal using BFS(queue)

Time Complexity: O(N) since we visit each node once
Space Complexity: O(N), more precisely the number of element on the last level, aka queue size when it’s a complete tree

#### Level order traversal using DFS(map)

Time Complexity: O(N) since we visit each node once
Space Complexity: O(lgN) because we are using a map and map size should be tree height, which worst case could be O(N)