Breadth First Search

bfs.py

# Leetcode  102  103
# Breadth First Search Simplest
def bfs(root):
    queue = [root]
    while queue:
        n = queue.pop(0)
        queue.append(n.left)
        queue.append(n.right)

# based on that, what we are deadling with might not be a perfect binary tree
# then what we can do is skip Null node
def bfs(root):
    queue = [root]
    while queue:
        n = queue.pop(0)
        if not n:
            continue
        queue.append(n.left)
        queue.append(n.right)


# based on that, if we want to keep track of the level
# then what we can do is
def bfs(root):
    queue = [ (root, 0) ]
    while queue:
        n, lvl = queue.pop(0)
        if not n:
            continue
        queue.append( (n.left, lvl + 1) )
        queue.append( (n.right, lvl + 1) )

# then we can think about the list we want to return
def bfs(root):
    queue = [ (root, 0) ]
    ret = []
    while queue:
        n, lvl = queue.pop(0)
        if not n:
            continue
        if len(ret) <= lvl: # when we meet the first element in a new layer
            ret.append( [] )
        ret[lvl].append(n.val)
        queue.append( (n.left, lvl + 1) )
        queue.append( (n.right, lvl + 1) )
    return ret