Level order traversal or breadth first traversal is traversing the same level nodes of a tree then move to next level. We can use queue to print the level order traversal of a binary tree.

Write a Java program to print the level order traversal of a binary tree.

Sometimes people say level order traversal as breadth first search (BFS) where they meant the same level order traversal of a tree.

binary tree level order traversal

For above tree the level order traversal or breadth first traversal will give below output

Output: 1 2 3 4 5 6 7

Binary Tree Level Order Traversal

Algorithm for Level Order Traversal of Tree

Step1: Add the Root Node in a Queue
Step2: Loop through the Queue till its not empty
Step3: Dequeue the Node from the Queue, name it temp
Step4: Print temp’s Data
Step5: If temp has Left Child then Add left child in Queue
Step6: If temp has Right Child then Add right child in Queue
Step7: Goto Step 2

Demonstration of Algorithm

Here is binary tree level order traversal steps shown using diagram. Go through every step and understand it. I bet you will remember this forever.

Below is the Tree with root = Node 1. And we have an empty queue

binary tree level order traversal

We will add root element in the queue. So Node 1 will be moved to the queue.

binary tree level order traversal

Now we will dequeue the element and temp will be pointing to Node 1 and Node 2 and Node 3 are left and right child of Node 1. We will Print temp.data to Print 1

binary tree level order traversal

Left and Right child of Node 1 will be added in the queue. So Node 2 and Node 3 will be inserted in the queue.

binary tree level order traversal

Now we will dequeue and temp will be pointed to Node 2. Print Node 2.

binary tree level order traversal

Now Node 2 has Node 4 and Node 5 as left and right child so we will add them in the queue.

binary tree level order traversal

Now we will dequeue Node 3 and Print 3. Noe temp is pointing to Node 3 and its left and right child are Node 6 and Node 7. 

binary tree level order traversal

We will add Node 6 and Node 7 in the Queue.

binary tree level order traversal

Now we will dequeue Node 4 and Print it. As there are no children for Node 4 so nothing will be added in the queue.

binary tree level order traversal

Now we will dequeue Node 5 and Print it. As there are no children for Node 5 so nothing will be added in the queue.

binary tree level order traversal

Now we will dequeue Node 6 and Print it. As there are no children for Node 6 so nothing will be added in the queue.

binary tree level order traversal

Now we will dequeue Node 7 and Print it. As there are no children for Node 7 so nothing will be added in the queue.

binary tree level order traversal

Now as the queue is empty so control will come out of the while loop. And we will see that our java code has printed the binary tree level order traversal.

Java Code for Level Order Traversal

Java Code


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

class Node {
    String data;
    Node left;
    Node right;
    Node rightNext;

    public Node(String data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
        this.rightNext = null;
    }
}

class BinaryTree {
    public Node CreateTree()
    {
        Node n1 = new Node("1");
        Node n2 = new Node("2");
        Node n3 = new Node("3");
        Node n4 = new Node("4");
        Node n5 = new Node("5");
        Node n6 = new Node("6");
        Node n7 = new Node("7");

        n1.left = n2;
        n1.right = n3;

        n2.left = n4;
        n2.right = n5;

        n3.left = n6;
        n3.right = n7;

        return n1;
    }

    public void PrintLevelOrder(Node root)
    {
        System.out.print("Print Level Order ");
        Queue<Node> queue = new LinkedList<>();

        queue.add(root);

        while(!queue.isEmpty())
        {
            Node temp = queue.remove();
            System.out.print(temp.data + " ");
            if(temp.left!=null)
                queue.add(temp.left);
            if(temp.right!=null)
                queue.add(temp.right);
        }
        System.out.println();
    }
}

public class test {

    public static void main(String[] args) {
        
        BinaryTree bt = new BinaryTree();
        Node root = bt.CreateTree();

        bt.PrintLevelOrder(root);
    }
}
Try It

Dry Run for above java program

Steps involved to print level order traversal of a binary tree

  1. If root is not null then add the root in the queue.
  2. Node 1 will be added in the Queue.
  3. Queue is not empty so remove the node from the queue.
  4. We will have Node 1 with us. Print Node 1.
  5. If Node 1 has left and right child then add them in the queue.
  6. Node 2 and 3 will get added in the Queue.
  7. Now Queue is not empty so remove the node from the queue
  8. We will get Node 2 with us. Print Node 2.
  9. If Node 2 has left and right child then add them in the queue.
  10. Node 4 and 5 will be added in the Queue.
  11. Queue contains currently Node 3, Node 4 and Node 5
  12. Queue is not empty so remove the node from the queue
  13. We will get Node 3 with us. Print Node 3.
  14. If Node 3 has left and right child then add them in the queue.
  15. Node 6 and 7 will get added in the queue.
  16. Queue contains currently Node 4, Node 5, Node 6, Node 7
  17. Queue is not empty so remove the node from the queue.
  18. We will get Node 4. Print Node 4.
  19. If Node 4 has left and right child then add them in the queue.
  20. Nothing will be added in the queue because Node 4 has no children.
  21. Queue is not empty so remove the node from the queue.
  22. We will get Node 5. Print Node 5.
  23. If Node 5 has left and right child then add them in the queue.
  24. Nothing will be added in the queue because Node 5 has no children.
  25. Queue is not empty so remove the node from the queue.
  26. We will get Node 6. Print Node 6.
  27. If Node 6 has left and right child then add them in the queue.
  28. Nothing will be added in the queue because Node 6 has not children.
  29. Queue is not empty so remove the node from the queue.
  30. We will get Node 7. Print Node 7.
  31. If Node 7 has left and right child then add them in the queue.
  32. Nothing will be added in the queue because Node 7 has no children.
  33. Queue is empty so break the loop.

Conclusion

Above java code to print the Level order traversal of a binary tree in Java. This will print all the nodes of the above binary tree in linear time. Time complexity of the above code will be O(n). Because we are using a queue to the Space complexity will be O(n) where n is the number of nodes of the binary tree.



References

https://en.wikipedia.org/wiki/Tree_traversal

LEAVE A REPLY

Please enter your comment!
Please enter your name here