In post talks about Breadth-First Search or BFS for a Graph Data Structure with example
To solve problems on graphs, we need a mechanism for traveling the graph. graph traversal algorithms are usually called Graph Search Algorithms. like trees traversal algorithms( inorder, preorder, and level order traversals), Graph Search algorithms can be thought of As starting at some source vertex in a graph and searching the graph by going through the edges and marking the vertices. We have mainly two search algorithms for traveling the graphs
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
In this post, we will learn how to write a Java program for a Binary tree traversal using breadth-first search which is also known as level order traversal of binary tree
Breadth-First Search (BFS)
Contrary to the Depth-First Search(DFS) where traversal is done by moving to the node in the next level, in Breadth-First Search(BFS) all the nodes with in the same level are visited then only next level is visited.
For depth search Java program you can refer to this post- Depth-First Search or DFS for a Graph Data Structure
The level order traversal of the binary tree as per the above image is as follows:
Level 0 – 60
Level 1- 30, 70
Level 2- 25, 38, 61, 85
Level 3- 10, 28, 32
Breadth-First Search (BFS) Program can be implemented using two approaches:
- Recursive Approach
- Non-recursive Approach
Breadth-First Search (BFS) Recursive Approach Source Code:
To write a Java program using a recursive approach to do a level order traversal of a binary tree We need to find the height of the tree and then call method for level order traversal for level 0 to max level of the binary tree.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** * Function for level order traversal */ public void levelOrder(){ int heightOfTree = findTreeHeight(root); for(int i = 0; i < heightOfTree; i++){ levelOrderTraversalOfBinaryTree(root, i); } } /** * Recursive method of level order traversal * @param node tree * @param level level of tree */ private void levelOrderTraversalOfBinaryTree(Node node, int level){ if(node == null){ return; } if(level == 0){ System.out.print(node.value + " "); }else{ levelOrderTraversalOfBinaryTree(node.left, level-1); levelOrderTraversalOfBinaryTree(node.right, level-1); } } |
Breadth-First Search (BFS) Non-Recursive Approach Source Code:
To write a Java program for level order traversal of a binary tree using a non-recursive method a queue is used. Initially, the root of the tree is inserted into the queue then you need to do the following until the queue is empty.
- We have to poll a node from the queue and display its value.
- We have to check if the node has left child, if yes then add that to the queue.
- Finally, we have to check if the node has the right child, if yes then add that to the queue.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** * Iterative function for level order traversal * @param root tree */ public void levelOrderTraversalOfBinaryTree(Node root){ //If Tree is empty if(root == null){ return; } //If Tree is not empty Queue<Node> q = new LinkedList<Node>(); q.add(root); while(!q.isEmpty()){ Node node = q.poll(); System.out.print(node.value + " "); if(node.left != null){ q.add(node.left); } if(node.right != null){ q.add(node.right); } } } |
Below is the Complete Source code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
package com.kkjavatutorials.client; import java.util.LinkedList; import java.util.Queue; public class BreadthFirstSearch { //Root node of the tree private Node root; public BreadthFirstSearch(){ root = null; } /** * This internal class representing binary tree nodes * @author KK JavaTutorials */ private static class Node{ private int value; private Node left; private Node right; public Node(int value){ this.value = value; left = null; right = null; } } /** * Function to insert node in tree * @param data to insert in binary tree */ public void insert(int data){ root = insert(root, data); } private Node insert(Node node, int data){ //If root node is null if(node == null){ return new Node(data); } /* Insert Node to the left if passed value is less than the current node*/ if(data < node.value){ node.left = insert(node.left, data); } /*Insert Node to the right if passed value is greater than the current node*/ else if(data > node.value){ node.right = insert(node.right, data); } //Finally return node which holds entire tree return node; } /** * Function to get height of the tree * @param root tree * @return height of tree */ public int findTreeHeight(Node root){ //if root is empty if(root == null){ return 0; }else{ // Find Height of left subtree int heightOfLeftSubtree = findTreeHeight(root.left); //Find Height of right subtree int heightOfRightSubtree = findTreeHeight(root.right); //Find Height in each recursive call return Math.max(heightOfLeftSubtree, heightOfRightSubtree) + 1; } } /** * Function for level order traversal */ public void levelOrder(){ int heightOfTree = findTreeHeight(root); for(int i = 0; i < heightOfTree; i++){ levelOrderTraversalOfBinaryTree(root, i); } } /** * Recursive method of level order traversal * @param node tree * @param level level of tree */ private void levelOrderTraversalOfBinaryTree(Node node, int level){ if(node == null){ return; } if(level == 0){ System.out.print(node.value + " "); }else{ levelOrderTraversalOfBinaryTree(node.left, level-1); levelOrderTraversalOfBinaryTree(node.right, level-1); } } /** * Iterative function for level order traversal * @param root tree */ public void levelOrderTraversalOfBinaryTree(Node root){ //If Tree is empty if(root == null){ return; } //If Tree is not empty Queue<Node> q = new LinkedList<Node>(); q.add(root); while(!q.isEmpty()){ Node node = q.poll(); System.out.print(node.value + " "); if(node.left != null){ q.add(node.left); } if(node.right != null){ q.add(node.right); } } } public static void main(String[] args) { //Create an Instance of BreadthFirstSearch BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch(); breadthFirstSearch.insert(60); breadthFirstSearch.insert(70); breadthFirstSearch.insert(30); breadthFirstSearch.insert(25); breadthFirstSearch.insert(38); breadthFirstSearch.insert(10); breadthFirstSearch.insert(28); breadthFirstSearch.insert(32); breadthFirstSearch.insert(61); breadthFirstSearch.insert(85); //Find Height of Binary Tree System.out.println("Height Of Tree: " + breadthFirstSearch.findTreeHeight(breadthFirstSearch.root)); //Print Level order traversal using recursive Method System.out.println("Level order traversal using recursive method"); breadthFirstSearch.levelOrder(); System.out.println(""); //Print Level order traversal using iterative Method System.out.println("Level order traversal using iterative method"); breadthFirstSearch.levelOrderTraversalOfBinaryTree(breadthFirstSearch.root); } } |
The Output of this Program:
Height Of Tree: 4
Level order traversal using recursive method
60 30 70 25 38 61 85 10 28 32
Level order traversal using iterative method
60 30 70 25 38 61 85 10 28 32
Advantages of BFS
A BFS can be used to find the shortest path between the starting point and any other reachable node.
Disadvantages of BFS
A Breadth-First Search(BFS) on a binary tree usually requires more memory than a DFS.
Application of BFS
Finding all connected components in a graph
Finding all nodes within one connected component
Finding the shortest path between two nodes
Comparing DFS and BFS Algorithms:
The big advantage of DFS is that it has much lower memory requirements than BFS because it’s not required to store all of the children pointers at each level. Depending on the data and what we are looking for, either DFS and BFS can be advantageous. For example in a family tree if we are looking for someone who is still alive and if we assume that person would be at the bottom of the tree then DFS is a better choice. BFS usually takes a very long time to reach that last level.
The DFS algorithm finds the goal faster. Now if we are looking for a family member who died a very long time ago then the person would be closer to the top of the tree. In this case, BFS finds faster than the DFS. S0 the advantages of either vary depending on the data and what we are looking for. DFS is related to the preorder traversal of a tree. Like preorder traversal, DFS digits each node before its children. The BFS algorithm works similarly to the level order traversal of the trees.
If someone asks that the DFS is better or BFS is better. The answer depends on the type of problem that they are trying to solve. BFS visits each level one at a time and if we know the solution we are searching for is at low depth then BFS is good. DFS is a better choice if the solution is maximum depth. The below table shows the difference between DFS and BFS in terms of their applications
| Applications | DFS | BFS |
| Spanning forest, connected components, paths, cycles | YES | YES |
| Shortest Paths | YES | |
| Minimal use of memory space | YES |
You May Also Like:
Introduction to Graph Data Structure?
Important Types of Graph Data Structure
Breadth-First Search or BFS for a Graph Data Structure
That’s all about Breadth-First Search or BFS for a Graph Data Structure
If you have any feedback or suggestion please feel free to drop in below comment box.