> Interview Breeze

Breadth First Search

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:

example Breadth First Search of a binary 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:
            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)))


You may also want to read:

Discerning a tree from a graph

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.

Depth First Search

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

Binary Tree Column Printer

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.