Level Order Traversal program in Java or BFT Program in Java

Traversing a binary tree can be done in various ways, and one of the most intuitive methods is Level Order Traversal. This method, also known as Breadth-First Traversal, processes nodes level by level, starting from the root. In this post, we’ll dive deep into how to implement Level Order Traversal in Java.

What is Level Order Traversal?

Level Order Traversal is a way of visiting all the nodes of a binary tree level by level. Starting from the root, we visit all nodes at the current depth level before moving on to the nodes at the next depth level. This method is particularly useful for tasks that require examining nodes in a hierarchical structure layer by layer.

Example Binary Tree

Consider this binary tree:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

A Level Order Traversal of this tree would produce the sequence: 1 2 3 4 5 6 7.

Java Implementation

1. Define the TreeNode Class

First, we need a class to represent each node in the binary tree.

class TreeNode {
    int value;
    TreeNode left, right;

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

2. Implement the Level Order Traversal

We use a queue to facilitate the traversal. The queue helps in processing each node level by level.

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

public class LevelOrderTraversal {

    // Function to perform level order traversal of the binary tree
    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        // Create a queue to hold the nodes
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            // Remove the front node of the queue
            TreeNode currentNode = queue.poll();
            System.out.print(currentNode.value + " ");

            // Add the left child to the queue
            if (currentNode.left != null) {
                queue.add(currentNode.left);
            }

            // Add the right child to the queue
            if (currentNode.right != null) {
                queue.add(currentNode.right);
            }
        }
    }

    public static void main(String[] args) {
        // Create a sample binary tree
        //         1
        //       /   \
        //      2     3
        //     / \   / \
        //    4   5 6   7
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("Level Order Traversal of the binary tree:");
        levelOrderTraversal(root);
    }
}

3. How the Code Works

TreeNode Class: Represents each node in the binary tree with an integer value and pointers to left and right children.
Queue Initialization: A Queue is used to keep track of nodes to visit. Nodes are processed in the order they are added to the queue (FIFO).
Main Traversal Loop:
Start with the root node in the queue.
Process each node by:
- Printing its value.
- Adding its left and right children to the queue (if they exist).
Main Method: Creates a sample binary tree and initiates the traversal.

Still cant able to understand is step by step breakdown of this program

Level Order Traversal program Step by Step Guide in Java

4. Output

Running this code will give us the level order traversal of the binary tree:

Level Order Traversal of the binary tree:
1 2 3 4 5 6 7

5. Enhanced Version: Printing Levels Separately

If you want to print each level of the tree on a new line, you can modify the levelOrderTraversal function as follows:

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 currentNode = queue.poll();
            System.out.print(currentNode.value + " ");

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

            if (currentNode.right != null) {
                queue.add(currentNode.right);
            }
        }
        System.out.println();  // Move to the next line after printing each level
    }
}

Output for Enhanced Version

Level Order Traversal of the binary tree:
1 
2 3 
4 5 6 7

Understanding `queue.poll()`

poll(): Removes and returns the head of the queue. If the queue is empty, it returns null. This operation is key for traversing the tree level by level. Each node is processed and removed from the queue, allowing its children to be added for future processing.

Conclusion

Level Order Traversal is a foundational concept in tree and graph algorithms. It provides an efficient way to explore nodes level by level, making it ideal for problems that require hierarchical exploration. Implementing this in Java using a queue helps manage nodes in a clear and structured way, ensuring all nodes are visited in the correct order.

Feel free to experiment with the code by creating different binary trees or enhancing the traversal method for more advanced use cases.

I hope this guide helps you understand and implement Level Order Traversal in Java! If you have any questions or suggestions, please leave a comment below. Happy coding!