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