# Leetcode patterns — BFS

`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`

# BFS with Tree

`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`
`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`
`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`

# BFS with metrix

`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`

# BFS with key-value mapping

--

--

A Senior Software Developer/Body builder . to help others enjoy coding and stay healthy

Love podcasts or audiobooks? Learn on the go with our new app.

## LORY

A Senior Software Developer/Body builder . to help others enjoy coding and stay healthy