# Grokking the Coding Interview's Tree Breath First Search

Binary tree level order traversal, Reverse level order traversal, Zigzag traversal, Level averages, Minimum depth, Maximum depth, Level order successor

### 1. Given a binary tree, populate the values of all nodes of each level from left to right in separate sub-arrays.

Example:

```
- Input:
1
2 3
4 5
Output: []interface{}{[]interface{}{1}, []interface{}{2, 3}, []interface{}{4, 5}}
```

Approach:

```
- Start by pushing the root node to the queue.
- Keep iterating until the queue is empty.
- At each step,
- send the front of the queue and dequeue it
- enqueue its left and right child
```

Cost:

```
- O(n) time, O(n) space.
```

### 2. Given a binary tree, populate the values of all nodes of each level in reverse order in separate sub-arrays.

Example:

```
- Input:
1
2 3
4 5
Output: []interface{}{[]interface{}{4, 5}, []interface{}{2, 3}, []interface{}{1}}
```

Approach:

```
- Similar to level order reversal problem, except we append the current level's
value at the beginning of the output list.
```

Cost:

```
- O(n) time, O(n) space.
```

### 3. Given a binary tree, populate the values of all nodes of each level in a zigzag order in separate sub-arrays.

Example:

```
- Input:
1
2 3
4 5
Output: [][]interface{}{[]interface{}{1}, []interface{}{3, 2}, []interface{}{4, 5}}
```

Approach:

```
- Start by pushing the root node to a queue.
- Keep iterating until the queue is empty.
- At each step,
- use a linked list to push front or back depending on the zigzag direction
- enqueue its left and right child
```

Cost:

```
- O(n) time, O(n) space.
```

### 4. Given a binary tree, populate an array to represent the averages of all of its levels.

Example:

```
- Input:
1
2 3
4 5
Output: []float64{1, 2.5, 4.5}
```

Approach:

```
- Similar to level order traversal problem, except we keep track of the sum
at each level and return the average in the end.
```

Cost:

```
- O(n) time, O(n) space.
```

### 5. Given a binary tree, find the minimum depth, aka the number of nodes along the shortest path from the root node to the nearest leaf node.

Example:

```
- Input:
1
2 3
4 5
6 7
8
Output: 3
```

Approach:

```
- Similar to level order traversal problem, except we keep track of the minimum
depth at each level
- Return it immediately once we find the leaf node.
```

Cost:

```
- O(n) time, O(n) space.
```

### 6. Given a binary tree, find the maximum depth.

Example:

```
- Input:
1
2 3
4 5
6 7
8
Output: 5
```

Approach:

```
- Similar to minimum depth problem, we will keep traversing for all
levels, incrementing our maximum depth instead of returning as
soon as we find a leaf node.
```

Cost:

```
- O(n) time, O(n) space.
```

### 7. Given a binary tree and a node, find the level order successor of the given node. The level order successor is the node that appears right after the given node in the level order traversal.

Example:

```
- Input: target=6, tree=
1
2 3
4 5
6 7
8
Output: 6
```

Approach:

```
- Similar to level order traversal problem, except we will not keep
track of all the levels.
- Instead, we keep inserting the child node to the queue and return
the next node as soon as we find the target.
```

Cost:

```
- O(n) time, O(n) space.
```

For more coding problems, please visit https://github.com/hoanhan101/algo.

Tagged: #grokking-the-coding-interview, #algorithm