5 months, 1 week

# Coding Patterns: Breadth First Search

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

This pattern is very useful to solve the problems involving traversal of a tree in a level-by-level order

## Problem: Binary Tree Level Order Traversal

LeetCode 102 - Binary Tree Level Order Traversal [medium]

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

We can use a Queue to efficiently traverse in BFS fashion. Here are the steps of our algorithm:

Start by pushing the root node to the queue.
Keep iterating until the queue is empty.
In each iteration, first, count the elements in the queue.

We will have these many nodes at the current level.
Next, remove level_size nodes from the queue and push their value into an array to represent the current level.
After removing each node from the queue, insert both of its children into the queue.
If the queue is not empty, repeat step 3 for the next level.

Solution:

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return None
q = [root]
ret = []
while q:
temp = []
for i in range(len(q)):
node = q.pop(0)
temp.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ret.append(temp)
return ret

Time ComplexityO(n) where n is the total number of nodes in the tree.

Space ComplexityO(n), since we need an O(n) space to return the result. We will also need O(n) for the queue.

When the problem asks for the traversal of a tree, you should think about BFS pattern and use it in combination with the Queue structure.

LeetCode 104 - Maximum Depth of Binary Tree [easy]

Given the `root` of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

1.Solution:

class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
maxD = 0
queue = []
if root is not None:
queue.append(root)
while len(queue) > 0:
for i in range(len(queue)):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
maxD += 1
return maxD

2. Solution:

class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

LeetCode 107 - Binary Tree Level Order Traversal II [easy]

Given the `root` of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Solution:

class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
q = collections.deque()
q.append(root)
res = []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
if node:
q.append(node.left)
q.append(node.right)
level.append(node.val)
if level:
res.append(level)
return res[::-1]

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Solution:

class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque()
queue.append([root, 1])
while queue:
for i in range(len(queue)):
curr, depth = queue.popleft()
if not curr.left and not curr.right:
return depth
if curr.left:
queue.append([curr.left, depth+1])
if curr.right:
queue.append([curr.right, depth+1])
return 0

LeetCode  637- Average of Levels in Binary Tree

Given the `root` of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within `10-5` of the actual answer will be accepted.

Solution:

class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
res = []
queue = [root]
while queue:
temp = []
sumVal = 0
for node in queue:
sumVal += node.val
if node.left:
temp.append(node.left)
if node.right:
temp.append(node.right)
res.append(sumVal / len(queue))
queue = temp
return res

#### Responses(0)  Related