Tree: Breadth First Search

Problem: Write code for doing a breadth first search in a Tree data structure.

Solution: Breadth first search inspects items one level at a time starting with the root node. This is unlike the Depth First Search where the nodes in the left most branch are visited until there are no more nodes and then backtracks.

The problem with implementing a breadth first search is that we have to remember the list of nodes at the same level before moving to the next level. This can be achieved by using a queue data structure. See this post on details of how to implement a Queue using an array. Every time we visit a node, we inspect the data contained in the node before Enqueueing both children to the Queue. If the node contains the data we were searching for we return the pointer to that node.

//Breadth First Search (BFS) method searches the tree one level at a time

Node * Breadth-First-Search(Node *root, int searchValue)
{
    Queue queue;
    queue.Enqueue(root);
    Node * currentNode;
    while(currentNode = queue.Dequeue())
    {
       if(currentNode->data == searchVal)
           return currentNode;

       queue.Enqueue(currentNode->left);
       queue.Enqueue(currentNode->right);
    }
}