# Leetcode patterns — BFS

After finished 1000 medium level problems. write down the patterns i have learned .

Continue with Previous article . here is another classic algorithm — BFS

In this article i will list all the high ranking problems to explain the classic pattern of BFS leetcode problems ,again, you do not have to solve all the problems, solve the high ranking problems first, focus on learning the patterns and ideas behind the problem itself.

Also , not all patterns could be useful in our day to day work (linklist, bitmask, math, etc) , if just for fun, still can solve other issues later on.

Lets start .

Core idea

`def bfs():`

q = [start_nodes]

while q:

nexts = []

while q:

n = q.pop(0)

result= do_something(n)

nexts.extend(next_level_nodes(n))

q = nexts

return result

Similar to DFS. the purpose is search . difference is DFS during search wants to go as deep as possible; BFS wants to collect the accessible nodes as wide as possible. maintein a queue is being processed , during each processing , get the next neightbor(or child) nodes .

With above 3 pattern, there are 3 sub patterns, differentiate by searching data structure : Tree, metrix, key-value

# BFS with Tree

Start from root, process the nodes level by level. keep the children into queue for next time processing .

`def bfs(root):`

q= [root]

res=[]

res.append([root.val])

while q :

child=[]

while q:

n = q.pop(0)

# do something to current

if n.children:

child.extend(n.children)

if child:

# do something to children

q=child

return res

Sample

429. N-ary Tree Level Order Traversal

Goal : Find every level children and add to result . This is classic BFS model . Though process is simple, start from root, collect every level children, add every level nodes into result .

`def levelOrder(self, root: 'Node') -> List[List[int]]:`

if not root:

return []

q= [root]

res=[]

res.append([root.val])

while q :

child=[]

while q:

n = q.pop(0)

if n.children:

child.extend(n.children)

if child:

res.append([x.val for x in child])

q=child

return res

Another sample

Thought process: start from root node , track the depth ,once reach the depth , insert row of values . Need handle 3 Case : insert at 1st row, insert at middle, insert at last row.

My Submittion

`def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:`

"""

Case1 : insert at root

Case2 : insert at last row

Case3 : insert betwwn first and last row

"""

if not root:

return []

if depth == 1: # Case1

return TreeNode(val, root)

q = [root]

last_row = []

d=1

def insert(n, val):

left, right = n.left, n.right #original left and right

n.left = TreeNode(val, left=left) #left=new_node, new_node'left = original left

n.right = TreeNode(val, right=right)#right=new_node, new_node'right = original right

return n

while q:

if d == depth-1: # Case3

for n in q:

n=insert(n, val)

return root

else:

child = []

while q:

n = q.pop(0)

if n.left:

child.append(n.left)

if n.right:

child.append(n.right)

q = child

if q:

last_row = q

d+=1

for n in last_row: # Case2

n=insert(n, val)

return root

Other high ranking Tree BFS problems :

919. Complete Binary Tree Inserter

958. Check Completeness of a Binary Tree

102. Binary Tree Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal

107. Binary Tree Level Order Traversal II

199. Binary Tree Right Side View

116. Populating Next Right Pointers in Each Node

513. Find Bottom Left Tree Value

515. Find Largest Value in Each Tree Row

# BFS with metrix

Similar idea. difference is that input data structure is metrix . so the “next level” nodes is not children, is connected (left, right, up, down) cells .

Thought process: start with rotten oranges . collect neighbor fresh oranges, update state in metrix value (set to rotten) .

Submission :

def orangesRotting(self, grid: List[List[int]]) -> int:

# load the rotten into q

q = []

row, col = len(grid), len(grid[0])

for r in range(row):

for c in range(col):

if grid[r][c] == 2:

q.append((r,c))# find the neighbor oranges which could get rotten in next time

def get_next(r,c):

d = [(1,0),(0,1),(-1,0),(0,-1)]

nonlocal grid, row, col

res = set()

for d1 in d:

r1,c1 = r+d1[0], c+d1[1]

if r1 < 0 or c1 < 0 or r1 == row or c1 == col or grid[r1][c1] != 1:

continue

res.add((r1,c1))

return res

# BFS rotten the next

res = 0

while q:

nexts = set()

for r,c in q:

grid[r][c]=2

while q:

r,c = q.pop()

nexts|=get_next(r,c)

q = nexts

if not q: # handle last day

break

res+=1

# all must be rotten then consider success

for r in range(row):

for c in range(col):

if grid[r][c] == 1:

return -1

return res

Other high ranking metrix BFS problems :

417. Pacific Atlantic Water Flow (2 times BFS)

# BFS with key-value mapping

Similar idea, the “next nodes” need based on “bank”

## Last

That’s all .I believe you grabbed the idea of BFS .

Leetcode is fun and challenging, definally improved programming thinking. it’s worth to add to your weekly routine if you are developer and wants start competitive.

Thanks for reading, happy leetcoding !