Java Program for Level Order Tree Traversal

This Java program demonstrates how to perform a level order traversal on a binary tree. Level order traversal, also known as breadth-first traversal, visits each level of the tree from left to right. This method is particularly useful for creating a snapshot of the tree level by level.

Binary Tree Class

The BinaryTree class defines the structure of the binary tree and includes a method for level order traversal using a queue for a FIFO (first-in-first-out) approach.

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

public class BinaryTree {
    static class Node {
        int value;
        Node left, right;

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

    Node root;

    public BinaryTree() {
        root = null;
    }

    // Method for Level Order Traversal
    public void levelOrder() {
        if (root == null) return;

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

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

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

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

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

        System.out.println("Level order traversal:");
        tree.levelOrder();
    }
}

Explanation of the Level Order Traversal Method

• The method uses a Queue to keep track of nodes at each level starting from the root.
• Nodes are processed from the queue, their values are printed, and their left and right children (if any) are added to the queue.
• This ensures that nodes are visited level by level from left to right.

Conclusion

The level order traversal is essential for applications that require processing of a tree level by level, such as in certain graph algorithms or hierarchical data processing tasks. This Java implementation provides a clear and efficient method for accomplishing this task.