Breadth First Search

Breadth first search explores a tree or a Graph level by level. This is in contrast to Depth First Search where it explores the depth of a node first. BFS is implemented using a queue, appending the children to the end of the queue and processing the items at the front of the queue.

Python deque library

Use the python deque library for implementing queues.

Declare the queue with q = deque(). You can append values to the end of queue using q.append(value) and pop values from the front of the queue using q.popleft().

Binary Trees BFS Template

res = []
q = deque()
q.append(root)

while q:
	level = []
	qLen = len(q)
	for i in range(qLen):
		node = q.popleft()
		if node:
			level.append(node.val)
			q.append(node.left)
			q.append(node.right)
		if level:
			res.append(level)

return res

2D Matrix

directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ROWS, COLS = len(grid), len(grid[0])
area = 0

def bfs(r, c):
	q = deque() # 1. Initialize queue
	grid[r][c] = 0 
	q.append((r, c)) # 2. Add first element to queue

	while q:
		row, col = q.popleft() # 3. Get element at front of queue
		for dr, dc in directions:
			nr, nc = dr + row, dc + col
			if (nr < 0 or nc < 0 or nr >= ROWS or
				nc >= COLS 
			):
				continue
			q.append((nr, nc))
			# 4. Update question specific condition or counter
	return 

for r in range(ROWS):
	for c in range(COLS):
		bfs(r, c) # 0. Run BFS on this cell
		
return area