In this post we’ll see a Java program to do a Binary tree traversal using breadth first search which is also known as level order traversal of binary tree.
Breadth first search
Contrary to the depth first search where traversal is done by moving to node in the next level, in breadth first search all the nodes with in the same level are visited then only next level is visited.
For depth search Java program refer this post- Binary Tree Traversal Using Depth First Search Java Program
The level order traversal of the binary tree, in the above image will happen in the following order-
- Level 0 – 50
- Level 1- 30, 70
- Level 2- 15, 35, 62, 87
- Level 3- 7, 22, 31
Breadth first Java program for a binary tree can be written using both-
Breadth first search Recursive Java program
To write a Java program to recursively do a level order traversal of a binary tree you need to calculate height of the tree and then call method for level order traversal for level 0 to max level of the binary tree.
public void levelOrder(){
int height = calculateTreeHeight(root);
for(int i = 0; i < height; i++){
levelOrderTraversal(root, i);
}
}
// Method for breadth first search
public void levelOrderTraversal(Node node, int level){
if(node == null){
return;
}
if(level == 0){
System.out.print(node.value + " ");
}else{
levelOrderTraversal(node.left, level-1);
levelOrderTraversal(node.right, level-1);
}
}
Breadth first search Non-Recursive Java program
To write a Java program for level order traversal of a binary tree using an iterative method, a queue is used. Initially, root of the tree is inserted to the queue then you need to do the following until queue is empty.
- Poll a node from queue and display its value.
- Check if node has left child, if yes add that to the queue.
- Check if node has right child, if yes add that to the queue.
Iterative approach is considered more efficient than the recursive approach.
Binary Tree- Breadth first search Java program
Full Java program for breadth first search or level order traversal of binary tree.
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeBFS {
// first node
private Node root;
BinaryTreeBFS(){
root = null;
}
// Class representing tree nodes
static class Node{
int value;
Node left;
Node right;
Node(int value){
this.value = value;
left = null;
right = null;
}
public void displayData(){
System.out.print(value + " ");
}
}
public void insert(int i){
root = insert(root, i);
}
//Inserting node to tree using recursion
public Node insert(Node root, int value){
if(root == null){
return new Node(value);
}
// Move to the left if passed value is
// less than the current node
if(value < root.value){
root.left = insert(root.left, value);
}
// Move to the right if passed value is
// greater than the current node
else if(value > root.value){
root.right = insert(root.right, value);
}
return root;
}
// Method to get height of the tree
public int calculateTreeHeight(Node root){
if(root == null){
return 0;
}else{
// height of left subtree
int lsh = calculateTreeHeight(root.left);
// height of right subtree
int rsh = calculateTreeHeight(root.right);
// height in each recursive call
return Math.max(lsh, rsh) + 1;
}
}
public void levelOrder(){
int height = calculateTreeHeight(root);
for(int i = 0; i < height; i++){
levelOrderTraversalRec(root, i);
}
}
// Recursive Method for breadth first search
public void levelOrderTraversalRec(Node root, int level){
if(root == null){
return;
}
if(level == 0){
root.displayData();
}else{
levelOrderTraversalRec(root.left, level-1);
levelOrderTraversalRec(root.right, level-1);
}
}
// Iterative Method for breadth first search
public void levelOrderTraversalItr(Node root){
if(root == null){
return;
}
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty()){
Node node = queue.poll();
node.displayData();
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
public static void main(String[] args) {
BinaryTreeBFS bst = new BinaryTreeBFS();
bst.insert(50);
bst.insert(70);
bst.insert(30);
bst.insert(15);
bst.insert(35);
bst.insert(7);
bst.insert(22);
bst.insert(31);
bst.insert(62);
bst.insert(87);
System.out.println("Tree Height- " + bst.calculateTreeHeight(bst.root));
System.out.println("Level order traversal recursive");
bst.levelOrder();
System.out.println();
System.out.println("Level order traversal iterative");
bst.levelOrderTraversalItr(bst.root);
}
}
Output
Tree Height- 4 Level order traversal recursive 50 30 70 15 35 62 87 7 22 31 Level order traversal iterative 50 30 70 15 35 62 87 7 22 31
Time and space complexity of binary tree level order traversal
With the recursive approach shown in this post which uses the height of the tree the time complexity in worst case is O(n2). Calculation of tree height is O(n) operation if tree is skewed (not well balanced).
For each level i, recursive method takes a top down approach traversing almost the whole tree to find nodes at level i. Which again is O(n) operation. So the total time complexity because of nested loop is O(n2).
Recursion depth is at most the height of the tree h. So the space complexity of recursive approach is O(h) where h may equal n in case of a skewed tree, for balanced tree h equals log(n).
With the iterative approach where Queue data structure is used the time complexity is O(n) as each tree node is visited exactly once.
Space complexity with iterative method is also O(n), as Queue may store upto n/2 elements in worst case.
That's all for this topic Binary Tree Traversal Using Breadth First Search Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
Would have been great to mention time and space complexity.
ReplyDelete