Level Order Traversal program Step by Step Guide in Java

Program Explanation

1. Class Definition

public class LevelOrderTraversal {

This defines a public class named LevelOrderTraversal. It contains a static method levelOrderTraversal for performing level order traversal on a binary tree.

2. Function Definition

public static void levelOrderTraversal(TreeNode root) {

This is a static method which means it can be called without creating an instance of the LevelOrderTraversal class. It takes a single parameter root, which is the root node of the binary tree of type TreeNode.

3. Null Check

if (root == null) {
    return;
}

This checks if the root is null. If the tree is empty (i.e., root is null), the function returns immediately without performing any operations.

4. Queue Initialization

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

• Queue Initialization: A Queue is initialized using LinkedList. In Java, Queue is an interface, and LinkedList is a class that implements this interface, allowing us to use queue operations.
• Adding Root: The root node is added to the queue. The queue will help in managing the nodes to be processed in the order of their levels.

5. BFS Loop

while (!queue.isEmpty()) {

• Loop Condition: The loop runs as long as the queue is not empty. Each iteration processes one node.

6. Polling a Node

TreeNode currentNode = queue.poll();

• Polling: queue.poll() removes and returns the head (front) of the queue. If the queue is empty, poll returns null.
• Assigning to Current Node: The returned node is assigned to currentNode.
• poll() vs. peek(): poll() removes and returns the head of the queue, while peek() only returns the head without removing it.

7. Processing the Node

System.out.print(currentNode.value + " ");

• Printing: The value of currentNode is printed. This is part of the traversal output.

8. Adding Children

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

• Adding Left Child: If currentNode has a left child (currentNode.left is not null), it is added to the queue.
• Adding Right Child: Similarly, if currentNode has a right child (currentNode.right is not null), it is also added to the queue.

These children will be processed in subsequent iterations of the loop.

9. End of Loop and Function

The loop continues until all nodes have been processed, i.e., the queue is empty. Once all nodes are processed, the function completes, and the entire tree has been traversed in level order.

Logical Flow

1. Initialization: Start by adding the root node to the queue.
2. Processing: Repeatedly remove the front node of the queue.

• Print its value.
• Add its children to the queue if they exist.

1. Termination: The process continues until the queue is empty, meaning all levels have been processed.

Poll Method

• poll() Method: This is part of the Queue interface in Java. It retrieves and removes the head of the queue. If the queue is empty, it returns null. This method is crucial for BFS (Breadth-First Search) because it allows processing nodes level by level. Each call to poll() gives the next node to process, maintaining the FIFO (First In, First Out) order.

Complete Example

To illustrate how the program works, let’s include the TreeNode class and the main method from the initial code example:

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

// Class representing a node in the binary tree
class TreeNode {
    int value;
    TreeNode left, right;

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

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);
    }
}

Easy Alternative Methods for printing BFT is Enhanced Version: Printing Levels Separately

This example sets up a simple binary tree and performs a level order traversal, printing each node’s value in level order.