Breadth-First Search BFS

Published in

DS Algo for novice

8 min readDec 3, 2020

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’[1]), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

BFS of the graph will be

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Applications of Breadth First Traversal

Shortest Path and Minimum Spanning Tree for unweighted graph In an unweighted graph, the shortest path is the path with the least number of edges. With Breadth-First, we always reach a vertex from a given source using the minimum number of edges. Also, in the case of unweighted graphs, any spanning tree is Minimum Spanning Tree and we can use either Depth or Breadth-first traversal for finding a spanning tree.
Peer to Peer Networks. In Peer to Peer Networks like BitTorrent, Breadth-First Search is used to find all neighbor nodes.
Crawlers in Search Engines: Crawlers build an index using Breadth-First. The idea is to start from the source page and follow all links from the source and keep doing the same. Depth First Traversal can also be used for crawlers, but the advantage with Breadth-First Traversal is, depth or levels of the built tree can be limited.
Social Networking Websites: In social networks, we can find people within a given distance ‘k’ from a person using Breadth-First Search till ‘k’ levels.
GPS Navigation systems: Breadth-First Search is used to find all neighboring locations.
Broadcasting in Network: In networks, a broadcasted packet follows Breadth-First Search to reach all nodes.
In Garbage Collection: Breadth-First Search is used in copying garbage collection using Cheney’s algorithm. Refer to this and for details. Breadth-First Search is preferred over Depth First Search because of the better locality of reference:
Cycle detection in the undirected graph: In undirected graphs, either Breadth-First Search or Depth First Search can be used to detect cycles. We can use BFS to detect a cycle in a directed graph also.
Ford–Fulkerson algorithm In the Ford-Fulkerson algorithm, we can either use Breadth-First or Depth First Traversal to find the maximum flow. Breadth-First Traversal is preferred as it reduces worst-case time complexity to O(VE2).
To test if a graph is Bipartite We can either use Breadth-First or Depth First Traversal.
Path Finding We can either use Breadth-First or Depth First Traversal to find if there is a path between two vertices.
Finding all nodes within one connected component: We can either use Breadth-First or Depth First Traversal to find all nodes reachable from a given node.

Many algorithms like Prim’s Minimum Spanning Tree and Dijkstra’s Single Source Shortest Path use structure similar to Breadth-First Search.

There can be many more applications as Breadth-First Search is one of the core algorithms for Graphs.

Implementation :

We can implement level order traversal in a recursive or an iterative way.

Recursive approach:

      /***********pseudocode*************/
/*Function to print level order traversal of tree*/
printLevelorder(tree)
for d = 1 to height(tree)
   printGivenLevel(tree, d);

/*Function to print all nodes at a given level*/
printGivenLevel(tree, level)
if tree is NULL then return;
if level is 1, then
    print(tree->data);
else if level greater than 1, then
    printGivenLevel(tree->left, level-1);
    printGivenLevel(tree->right, level-1);

Below is the java implementation for the same.

// Recursive Java program for level 
// order traversal of Binary Tree/* Class containing left and right child of current 
node and key value*/
class Node
{
 int data;
 Node left, right;
 public Node(int item)
 {
  data = item;
  left = right = null;
 }
}class BinaryTree
{
 // Root of the Binary Tree
 Node root;
 public BinaryTree()
 {
  root = null;
 }/* function to print level order traversal of tree*/
 void printLevelOrder()
 {
  int h = height(root);
  int i;
  for (i=1; i<=h; i++)
   printGivenLevel(root, i);
 }/* Compute the "height" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.*/
 int height(Node root)
 {
  if (root == null)
  return 0;
  else
  {
   /* compute height of each subtree */
   int lheight = height(root.left);
   int rheight = height(root.right);
   
   /* use the larger one */
   if (lheight > rheight)
    return(lheight+1);
   else return(rheight+1); 
  }
 }/* Print nodes at the given level */
 void printGivenLevel (Node root ,int level)
 {
  if (root == null)
   return;
  if (level == 1)
   System.out.print(root.data + " ");
  else if (level > 1)
  {
   printGivenLevel(root.left, level-1);
   printGivenLevel(root.right, level-1);
  }
 }
 
 /* Driver program to test above functions */
 public static void main(String args[])
 {
 BinaryTree tree = new BinaryTree();
 tree.root= new Node(1);
 tree.root.left= new Node(2);
 tree.root.right= new Node(3);
 tree.root.left.left= new Node(4);
 tree.root.left.right= new Node(5);
  
 System.out.println("Level order traversal of 
        binary tree is ");
 tree.printLevelOrder();
 }
}

Output is Level Order traversal of binary tree is 1 2 3 4 5

Time Complexity: O(n²) in worst case. For a skewed tree, printGivenLevel() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n²).
Space Complexity: O(n) in the worst case. For a skewed tree, printGivenLevel() uses O(n) space for call stack. For a Balanced tree, call stack uses O(log n) space, (i.e., the height of the balanced tree).

Iterative approach:-

Using queue.

printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
    a) print temp_node->data.
    b) Enqueue temp_node’s children 
      (first left then right children) to q
    c) Dequeue a node from q.

Below is the java implementation for the same:

// Iterative Queue based Java program to do level order traversal
// of Binary Tree/* importing the inbuilt java classes 
required for the program */
import java.util.Queue;
import java.util.LinkedList;/* Class to represent Tree node */
class Node {
 int data;
 Node left, right;
 public Node(int item) {
  data = item;
  left = null;
  right = null;
 }
}/* Class to print Level Order Traversal */
class BinaryTree {
Node root;/* Given a binary tree. Print its nodes in level order using array for implementing queue */
 void printLevelOrder() 
 {
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  while (!queue.isEmpty()) 
  {/* poll() removes the present head.   For more information on poll() visit http://www.tutorialspoint.com/java/ util/linkedlist_poll.htm */
   Node tempNode = queue.poll();
   System.out.print(tempNode.data + " ");/*Enqueue left child */
   if (tempNode.left != null) {
    queue.add(tempNode.left);
   }/*Enqueue right child */
   if (tempNode.right != null) {
    queue.add(tempNode.right);
   }
  }
 }public static void main(String args[]) 
 {
  /* creating a binary tree and entering 
  the nodes */
  BinaryTree tree_level = new BinaryTree();
  tree_level.root = new Node(1);
  tree_level.root.left = new Node(2);
  tree_level.root.right = new Node(3);
  tree_level.root.left.left = new Node(4);
  tree_level.root.left.right = new Node(5);System.out.println("Level order traversal of binary tree is - ");
  tree_level.printLevelOrder();
 }
}

Output is Level Order traversal of binary tree is 1 2 3 4 5

Time Complexity: O(n) where n is the number of nodes in the binary tree
Space Complexity: O(n) where n is the number of nodes in the binary tree

Building upon this level order approach, we will also solve below different problems:

Print each line nodes in a separate line:

Output for above tree should be
20
8 22
4 12
10 14

Solution:

/* An Iterative Java program to print levels line by line */import java.util.LinkedList; 
import java.util.Queue;public class LevelOrder 
{ 
 // A Binary Tree Node 
 static class Node 
 { 
  int data; 
  Node left; 
  Node right; 
  
  // constructor 
  Node(int data){ 
   this.data = data; 
   left = null; 
   right =null; 
  } 
 } 
 
 // Iterative method to do level order traversal line by line 
 static void printLevelOrder(Node root) 
 { 
  // Base Case 
  if(root == null) 
   return; 
  
  // Create an empty queue for level order tarversal 
  Queue<Node> q =new LinkedList<Node>(); 
  
  // Enqueue Root and initialize height 
  q.add(root); 
  
  
  while(true) 
  { 
   
   // nodeCount (queue size) indicates number of nodes 
   // at current level. 
   int nodeCount = q.size(); 
   if(nodeCount == 0) 
    break; 
   
   // Dequeue all nodes of current level and Enqueue all 
   // nodes of next level 
   while(nodeCount > 0) 
   { 
    Node node = q.peek(); 
    System.out.print(node.data + " "); 
    q.remove(); 
    if(node.left != null) 
     q.add(node.left); 
    if(node.right != null) 
     q.add(node.right); 
    nodeCount--; 
   } 
   System.out.println(); 
  } 
 } 
 
 // Driver program to test above functions 
 public static void main(String[] args) 
 { 
  // Let us create binary tree shown in above diagram 
 /*    1 
    /  \ 
    2  3 
    / \  \ 
   4  5  6 
  */
  
  Node root = new Node(1); 
  root.left = new Node(2); 
  root.right = new Node(3); 
  root.left.left = new Node(4); 
  root.left.right = new Node(5); 
  root.right.right = new Node(6); 
  
  printLevelOrder(root);}}

2. Bottom-up level order traversal:

For example:

Given binary tree  
    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

returns its bottom-up level order traversal as :
[
  [15,7],
  [9,20],
  [3]
]

Solution in java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public List < List < Integer >> levelOrderBottom(TreeNode root) {if (null == root) return new LinkedList < List < Integer >> ();List < List < Integer >> listAll = new LinkedList < >();
    Queue < TreeNode > queue = new LinkedList < >();
    queue.offer(root);
    List < Integer > list = new LinkedList < >();while (!queue.isEmpty()) {
      int size = queue.size();for (int i = 0; i < size; ++i) {
        TreeNode node = queue.poll();
        list.add(new Integer(node.val));
        if (null != node.left) {
          queue.offer(node.left);
        }
        if (null != node.right) {
          queue.offer(node.right);
        }}
((LinkedList) listAll).addFirst(new LinkedList < >(list));
      list.clear();}return listAll;
  }
}

References:-