# 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

623. Add One Row to Tree

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 .

994. Rotting Oranges

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)

542. 01 Matrix

# BFS with key-value mapping

433. Minimum Genetic Mutation

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 !

--

--

A channel which focusing on developer growth and self improvement