What is Level Order Traversal of a Binary Tree in Java?

In this article, we will learn Level Order Traversal of a Binary Tree in Java,This free JAVA tutorial for complete beginners will help you learn JAVA from scratch.

Level Order Traversal of a Binary Tree in Java

Zig-Zag level order traversal of Binary Tree after every K levels

Implementing a Binary Tree in Java

Binary Tree is a hierarchical data structure in which each node has at most two children and it can referred to as the left child and right child. It is called a tree because it resembles an inverted tree with the root at the top and branches extending downward.

In this article, we will learn to perform the Level Order Traversal of a Binary Tree.

Organization of the Binary Tree

In the Binary Tree each Node has Three Components:

Data: The value can be stored in the node.
Left Child: The reference to the left subtree which is itself a binary tree.
Right Child: The reference to the right subtree is also the binary tree.

Representation of the Binary Tree

Level Order Traversal

Level order traversal is the method used to the traverse the binary tree and it can visiting the level by level from left to right. It can uses the queue data structure to the keep track of the nodes to be visited.

The Algorithm is as follows:

Enqueue the root node.
While the queue is not empty then dequeue the node and visit it.
Enqueue its the left child(if its exists)
Enqueue its the right child(if its exists)
Repeat the steps 2-4 until the queue is empty.

Implementation of Level Order Traversal

Traversal: Level Order traversal visits the each node exactly once and it can making is O(n) in time complexity where the n is the number of Nodes. Space complexity is also O(n) due to the queue used for the traversal.

Program to Implement Level Order Traversal in Binary Tree

Java

// Java Program to Implement Traversing
// a Binary Tree in Level Order 
import java.util.LinkedList;
import java.util.Queue;

// Node Class
class Node {
    int data;
    Node left, right;

      // Constructor
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

// Binary Tree
class BinaryTree {
    Node root;

      // LevelOrder
    void levelOrder() {
        if (root == null)
            return;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

          // Traversing using queue 
        // To Traverse all the element according to the Level
        while (!queue.isEmpty()) {
            Node tempNode = queue.poll();
            System.out.print(tempNode.data + " ");

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

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

      // Main Function
    public static void main(String args[]) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(5);
        tree.root.left = new Node(3);
        tree.root.right = new Node(8);
        tree.root.left.left = new Node(1);
        tree.root.left.right = new Node(4);
        tree.root.right.left = new Node(7);
        tree.root.right.right = new Node(9);

        System.out.println("Level Order traversal of binary tree is ");
        tree.levelOrder();
    }
}

Output

Level Order traversal of binary tree is 
5 3 8 1 4 7 9

Complexity of the above Method

Time Complexity

Enqeueuing and dequeuing the each node takes the constant time is O(1).
For the binary tree with n nodes then the level order traversal visits the each node once resulting in the O(n) time complexity.
Space Complexity

The space complexity is O(n) where the n is the number of the nodes in binary tree.