Breadth first search (sometimes referred to as BFS) is an algorithm for traversing a graph or tree. We traverse the tree or graph by examining all nodes at a given level, before moving on to the next level of nodes. For example, imagine we had the following tree:

*The output of a breadth first traversal of this tree would be 1,2,3,4,5,6*

As you can see, with a breadth first search, we don't complete one subtree before moving down a new subtree, but instead step through all paths and sub trees one level at a time. This technique is especially useful for algorithms that are trying to find the shortest path between a set of nodes (though it comes at the cost of being more memory intensive).

Like depth first search, breadth First search can be implemented both recursively as well as non-recursively, though it is much easier to implement the non-recursive form of breadth first search by using a queue. We can see how to do this below:

class Node(): def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def bfs_print(node): queue = [node] while len(queue): next_queue = [] for cur_node in queue: print(cur_node.value) if cur_node.left: next_queue.append(cur_node.left) if cur_node.right: next_queue.append(cur_node.right) queue = next_queue test_node = Node(1, Node(2, Node(4)), Node(3, Node(5), Node(6))) bfs_print(test_node)

## You may also want to read:

Write a function that takes a node and returns True if the node is part of a tree or False if it's part of a graph.

Read More >>Depth first search (sometimes referred to as DFS) is an algorithm for traversing a graph or tree.

Read More >>Given binary tree, write a function to print its values in column order, from the bottom to top. You can assume that there will be no collisions, in which 2 nodes would occupy the same row and column.

Read More >>