Archived

breadth first search

An old note — I haven't updated it since I wrote it.

While a DFS explores down the branches of a tree, a BFS visits all the children of a given node, and then the children of those children, etc. level per level.

 1class Node:
 2    def __init__(self, val=-1, left=None, right=None):
 3        self.val = val
 4        self.left = left
 5        self.right = right
 6        
 7tree = Node('a', 
 8        Node('b', 
 9            Node('c', Node('d'), Node('e')),
10            Node('f', Node('g'), Node('h'))), 
11        Node('i', 
12            Node('j', Node('k'), Node('l')), 
13            Node('m', Node('n'), Node('o'))))

The code for a BFS is pretty straightforward to understand. We create a queue (any iterable container will do) initilised with the root.

We then iterate over it, and collect all the children (as long as they are not None), and assign the children container to the q container.

 1def BFS(root):
 2    q = [root]
 3    while q:
 4        children = []
 5        for node in q:
 6            print(node.val)
 7            if node.left:
 8                children.append(node.left)
 9            if node.right:
10                children.append(node.right)
11        q = children
12
13BFS(tree)

The pythonic one-liner is a little harder to stomach. To check whether the children are valid, in the list comprehension, we iterate over [node.left, node.right] once you've accepted that, it becomes are lot easier remembering and coding it up.

1def BFS(root):
2    q = [root]
3    while q:
4        for node in q:
5            print(node.val)
6        q = [child for node in q for child in [node.left, node.right] if child]