Tree Traversal - Breadth First Search

bfs.py

from collections import defaultdict

def iterative_bfs(tree, node, path=[]):
    """
    Iterative breadth first search
    """
    queue = [node]
    while queue:
        n = queue.pop(0)
        path.append(n)
        queue += tree[n]
    return path

# -------------------- #
#           1          #
#         / | \        #
#        2  3  4       #
#      /  \    | \     #
#     5    6   7  8    #
#    / \       | \     #
#   9   10     11 12   #
# -------------------- #
tree = defaultdict(list, {
    1: [2, 3, 4],
    2: [5, 6],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12]
})

print "iterative_bfs:", iterative_bfs(tree, 1)
# iterative_bfs:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]