# Breadth-First Search BFS

**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.- F
**ord–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

**or an**

*recursive***way.**

*iterative***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*/

classNode

{

int data;

Node left, right;

public Node(int item)

{

data = item;

left = right = null;

}

}classBinaryTree

{

// Root of the Binary Tree

Node root;

public BinaryTree()

{

root = null;

}/* function to print level order traversal of tree*/

voidprintLevelOrder()

{

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.*/

intheight(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 */

voidprintGivenLevel (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 */

classNode{

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 */

voidprintLevelOrder()

{

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 classLevelOrder

{

// 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 linestatic 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;

* }

* }

*/

classSolution{

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