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