Breadth First Traversal Or Level Order Traversal

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

Time complexity:

BFS require O(n) time as it visits every node exactly once.

Extra Space:

Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. 

Output : 1 2 3 4 5 6 7

Java Code:

package dataStructure.tree;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

/**

 * @author Rajendar Kumar

 *

 */

public class BFSWithQueue {

/**

* @param args

*/

public static void main(String[] args) {

Node rLl = new Node(null, 4, null);

Node rLr = new Node(null, 5, null);

Node rRl = new Node(null, 6, null);

Node rRr = new Node(null, 7, null);

Node rL = new Node(rLl, 2, rLr);

Node rR = new Node(rRl, 3, rRr);

Node root = new Node(rL, 1, rR);

List<Integer> list =bfs(root);

for (Integer integer : list) {

System.out.print(integer+" ");

}

}

public static List<Integer> bfs(Node root){

List<Integer> list = new ArrayList<>();

Queue<Node> hList = new LinkedList<>();

Node temp = root;

while(null != temp){

list.add(temp.key);

if(null != temp.left){

hList.add(temp.left);

}

if(null != temp.right){

hList.add(temp.right);

}

temp = hList.poll();

}

return list;

}

}

package dataStructure.tree;

/**

 * @author Rajendar Kumar

 *

 */

public class Node {

public int key;

public Node left;

public Node right;

public Node(Node left, int key, Node right) {

this.key = key;

this.left = left;

this.right = right;

}

}