How to implement Level Order Traversal of Binary Tree in Java? Example Tutorial

Hello guys, if you have worked in Java then you know that binary tree is one of the essential data structure and quite an important one for programmers, I even mentioned that on my 10 essential data structures for programmers articles.  Binary tree related question are also quite common on coding interviews and we are going to see one today but before that, let's revise what is binary tree? Binary trees are hierarchical data structures composed of nodes, each having at most two children: a left child and a right child. Traversing a binary tree in level order involves visiting nodes level by level, starting from the root. 

This traversal strategy is also known as breadth-first traversal. As I said, in this article, we'll explore how to perform the level order traversal of a binary tree in Java and discuss its applications, interview relevance, and tips for implementation.

How to implement Level Order Traversal in Java?

We will learn this by solving a problem. Given a binary tree represented by an array, the task is to print its nodes in level order, from the root to the deepest level. For example, consider the binary tree represented by the array [4, 10, 21, #, #, 18, 8]:

      4

     / \

    10  21

   / \    

  18  8

The level order traversal should output:

4

10 21

18 8

Solution

To implement level order traversal, we can use a queue data structure to keep track of the nodes at each level. Starting with the root node, we enqueue its children and continue the process until all nodes are visited.

Here is a simple Java program to achieve this

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

class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class LevelOrderTraversal {

    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) return;

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode current = queue.poll();
                System.out.print(current.val + " ");

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

            System.out.println(); // Move to the next level
        }
    }

    public static void main(String[] args) {
        // Example usage
        int[] treeArray = {4, 10, 21, -1, -1, 18, 8}; // -1 denotes null
        TreeNode root = buildTree(treeArray, 0);
        levelOrderTraversal(root);
    }

    private static TreeNode buildTree(int[] array, int index) {
        TreeNode root = null;
        if (index < array.length && array[index] != -1) {
            root = new TreeNode(array[index]);
            root.left = buildTree(array, 2 * index + 1);
            root.right = buildTree(array, 2 * index + 2);
        }
        return root;
    }
}

In this program, TreeNode is a class that defines the basic structure of a binary tree node. Each node has an integer value (val) and references to its left and right children. The constructor initializes the node with a given value.

The levelOrderTraversal() is a static method that takes the root of a binary tree as its parameter and prints the tree nodes in level order. The method uses a queue to perform level order traversal. It starts by enqueuing the root node.

Inside the while loop, it processes each level of the tree. The variable levelSize keeps track of the number of nodes at the current level. The inner for loop dequeues each node at the current level, prints its value, and enqueues its left and right children if they exist. 

After processing each level, a newline is printed to move to the next level.

In summary, this Java program demonstrates the level order traversal of a binary tree using a queue. The TreeNode class defines the structure of a tree node, and the levelOrderTraversal() method performs the traversal. 

The buildTree method is a helper function for constructing the binary tree from an array. The example in the main method showcases how to use these components

Where is Level Order Traversal Used?

Here are a couple of places where level order traversal is used, knowledge of these will hel pyou to better understand and remember this algorithm:

1. Breadth-First Search (BFS)

Level order traversal is a fundamental operation in BFS. It is widely used in graph algorithms to explore nodes level by level.

2. Binary Tree Printing

When visualizing binary trees, level order traversal provides a clear representation of nodes at each level, making it useful for printing trees in a human-readable format.

3. Shortest Path Algorithms

In certain scenarios, level order traversal can be used to find the shortest path between two nodes in a tree or a graph.

Here is also another visual example of level order traversal of a binary tree in Java:

Interview and Competitive Programming

Level order traversal is a common topic in technical interviews and competitive programming. Interviewers often use this problem to assess candidates' understanding of tree data structures, traversal algorithms, and basic queue operations. 

Here are some tips for tackling level order traversal-related questions:

1. Understand the Problem

Clearly understand the problem statement, especially the definition of level order traversal. Pay attention to the expected output format.

2. Use a Queue

The queue data structure is a key component in implementing level order traversal. Familiarize yourself with queue operations like enqueue and dequeue.

3. Handle Null Nodes

If the tree is represented using an array where certain positions are null, handle those cases appropriately to avoid errors.

4. Implement a Helper Function

Consider implementing a helper function to build the binary tree from the given array representation. This can make the main code cleaner.

5. Practice on Different Examples

Practice on various examples to solidify your understanding. Be comfortable with different tree structures.

6. Optimize for Space Complexity

Depending on the problem constraints, think about optimizing space complexity. For example, can you solve the problem without using additional data structures?

7. Discuss Your Approach

In an interview, communicate your thought process to the interviewer. Discuss your approach before diving into the code. This can lead to valuable insights and suggestions.

8. Edge Cases

Consider edge cases such as an empty tree, a tree with a single node, or skewed trees.

That's all about how to impalement level order traversal of binary tree in Java. By mastering the level order traversal of binary trees, you not only enhance your problem-solving skills but also gain a deeper understanding of tree structures and traversal algorithms. This knowledge is applicable in various domains of computer science, making it a valuable skill for both interviews and real-world applications.