Level Order tree Traversal implementation in Java

In this tutorial, we will learn what level order tree traversal is and how we can implement it in code in Java.

Level Order Traversal

In a level order traversal, we visit each of the nodes, level by level from left to right. In this method the nodes of level 1 are printed first, followed by nodes of level 2, till level ‘H’ where H is the height of the tree. We can implement this algorithm by storing each of the nodes in a queue data structure which is present in the java.util package. A queue follows a FIFO (First in First out) principle. Hence the element which is inserted first in the queue will be the first one to get popped out. You can visit the official documentation to learn more about Array Dequeue and Queue.

You can look at the example below:

Level Order tree Traversal implementation in Java

Code to implement Level order tree traversal in Java

import java.util.*;

class Node
{
  int value;
  Node left;
  Node right;

  public Node(int key)
  {
    value = key;
    left = null;
    right = null;
  }
}

class LevelOrderTraversal 
{
  public static void Traversal(Node root)
  {
    Queue<Node> queue = new ArrayDeque<>();
    queue.add(root);
    Node tempNode;

    while (!queue.isEmpty())
    {
      tempNode = queue.poll();
      System.out.print(tempNode.value + " ");

      if (tempNode.left != null) 
      {
        queue.add(tempNode.left);
      }

      if (tempNode.right != null)
      {
        queue.add(tempNode.right);
      }
    }
  }

  public static void main(String[] args)
  {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.left.left = new Node(7);
    root.right.left.right = new Node(8);
    root.right.right = new Node(9);

    System.out.print("The level order traversal of the tree is: ");
    Traversal(root);
  }
}

Output:

The level order traversal of the tree is: 1 2 3 4 5 6 9 7 8

Explanation of the above program

  1. Firstly we construct a tree.
  2. Next, we create an empty queue and add the root node to it.
  3. Then we process each node in the queue and add their left and right child nodes to the queue.
  4. The poll() method removes the first element in Queue and returns it.
  5. Hence all the nodes are processed in level order and are returned accordingly.

You can also read:

Leave a Reply

Your email address will not be published. Required fields are marked *