Breadth First Search in Binary Tree

Breadth First Search (BFS) is a very important algorithm for binary tree. So what does it mean? There are different ways we can search for a node in a binary tree. BFS is one of the those ways.

Specifically, BFS looks at nodes at lower depth first before moving on to the next depth. It is, in fact, level traversal. For example, lets take a look at the tree to your left. If we're to search for Node 3, the order that BFS goes is like this 5->2->8->0->1->3 (found!)

That's what a BFS is. Here is the algorithm for it. It is level traversal algorithm with a twist because we will stop as soon as we find the needed node.

public boolean binaryTreeBFS (Node root, int value)
{
  if (root == null)
    return false;

  LinkedList queue = new LinkedList();
  Node tempNode;
  queue.addLast(root);

  while (!queue.isEmpty())
  {
    tempNode = queue.remove();

    if (tempNode.data == value)
      return true;
    else
    {
      if (tempNode.left != null)
      queue.addLast(tempNode.left);

      if (tempNode.right != null)
      queue.addLast(tempNode.right);
    }
  }
  return false;
}

First we check the root. If it is null, then return false because there is nothing else to look for.

We then create a queue and a temporary node. The queue will store nodes according to their depth so that nodes of lower depth are always processed first.

Next, we loop search through every node in the queue, starting with the root. Thus, for every iteration, we remove the node at the beginning of our queue. If that node is what we're looking for then return true. Otherwise we'll add its children (nodes of lower level) to the end of the queue, so we can look at them later.

After looking at all nodes, if the needed node is not found yet, return false because it is not in the tree

As you might expect, in the worst case, this algorithm will take O(n) time where n is the number of nodes in the binary tree. The reason is that BFS has to look for every node.

That's all for now. If you have any question/suggestion please leave it in the comment section below :)