Tuesday, March 19, 2019

Binary Tree Traversal Using Breadth First Search Java Program

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-

  1. Level 0 – 50
  2. Level 1- 30, 70
  3. Level 2- 15, 35, 62, 87
  4. Level 3- 7, 22, 31

Binary Tree- Breadth first search Java program

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 a non-recursive 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.

  1. Poll a node from queue and display its value.
  2. Check if node has left child, if yes add that to the queue.
  3. Check if node has right child, if yes add that to the queue.

Full Java program for breadth first search or level order traversal of binary tree.

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    // first node
    private Node root;
    BFS(){
        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 - recursive method
    public Node insert(Node node, int value){
        if(node == null){
            return new Node(value);
        }
        // Move to the left if passed value is 
        // less than the current node
        if(value < node.value){
            node.left = insert(node.left, value);
        }
        // Move to the right if passed value is 
        // greater than the current node
        else if(value > node.value){
            node.right = insert(node.right, value);
        }
        return node;
    }
    
    // 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++){
            levelOrderTraversal(root, i);
        }
    }
    // Recursive 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);
        }    
    }
    
    // Iterative method for breadth first search
    public void treeLevelOrderTraversal(Node root){
        if(root == null){
            return;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node node = queue.poll();
            System.out.print(node.value + " ");
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
    }
    
    public static void main(String[] args) {
        BFS bst = new BFS();
        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("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.treeLevelOrderTraversal(bst.root);
        System.out.println("");
    }
}

Output

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 

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

  1. Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program
  2. Counting Sort Program in Java
  3. Print Odd-Even Numbers Using Threads And wait-notify - Java Program
  4. Find Duplicate Characters in a String With Repetition Count - Java Program
  5. Armstrong Number or Not Java Program

You may also like-

  1. Zipping Files And Folders in Java
  2. Java Lambda Expression Comparator Example
  3. How to Convert String to Date in Java
  4. Matrix Subtraction Java Program
  5. Batch Processing in Java JDBC - Insert, Update Queries as a Batch
  6. PermGen Space Removal in Java 8
  7. String Comparison in Java
  8. How to Inject Null And Empty String Values in Spring

No comments:

Post a Comment