Breadth-First Search BFS

Anil Thirunagari
Dec 3, 2020 · 8 min read

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

  1. 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.
  2. Peer to Peer Networks. In Peer to Peer Networks like BitTorrent, Breadth-First Search is used to find all neighbor nodes.
  3. 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.
  4. 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.
  5. GPS Navigation systems: Breadth-First Search is used to find all neighboring locations.
  6. Broadcasting in Network: In networks, a broadcasted packet follows Breadth-First Search to reach all nodes.
  7. 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:
  8. 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.
  9. 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).
  10. To test if a graph is Bipartite We can either use Breadth-First or Depth First Traversal.
  11. Path Finding We can either use Breadth-First or Depth First Traversal to find if there is a path between two vertices.
  12. 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:

  1. 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:-

DS Algo for novice

data structures and algorithms for beginners, cheatsheet

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store