1. What is Level Order Traversal?

Level Order Traversal is a type of Breadth-First Search (BFS) where we traverse a binary tree level by level, starting from the root and moving to the children from left to right.

2. Example

Given this binary tree:

        1
       / \
      2   3
     / \
    4   5

The level order traversal would be:

1 → 2 → 3 → 4 → 5

3. Why Use Level Order Traversal?

• Useful in printing nodes level by level
• Used in serialization/deserialization of trees
• Helps solve shortest path, distance, or width problems in trees
• Natural for finding parents, leaf nodes, and tree height

4. Concept: How Does It Work?

We use a queue to hold the nodes of each level. The queue ensures:

• Nodes are processed in the order they were added (FIFO).
• We enqueue children after processing the current node.

5. Algorithm Steps

• Initialize an empty queue.
• Enqueue the root node.
• While the queue is not empty:
  • Dequeue the front node.
  • Visit (process/print) the node.
  • Enqueue the left child (if exists).
  • Enqueue the right child (if exists).

6. Java Implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}


import java.util.*;

public class LevelOrderTraversal {

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  // Add root to queue

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();  // Remove front node
            System.out.print(current.val + " ");  // Visit

            // Add left and right children to queue
            if (current.left != null) queue.offer(current.left);
            if (current.right != null) queue.offer(current.right);
        }
    }

    public static void main(String[] args) {
        /*
              1
             / \
            2   3
           / \
          4   5
        */

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

        LevelOrderTraversal tree = new LevelOrderTraversal();
        System.out.println("Level Order Traversal:");
        tree.levelOrder(root);  // Output: 1 2 3 4 5
    }
}

7. Time and Space Complexity

Measure	Value
Time Complexity	O(n) – every node is visited once
Space Complexity	O(n) – queue holds all nodes in worst case (e.g., last level)

8. Level Order with Levels Separated

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

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

    while (!queue.isEmpty()) {
        int levelSize = queue.size();  // Number of nodes at current level

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

            if (current.left != null) queue.offer(current.left);
            if (current.right != null) queue.offer(current.right);
        }
        System.out.println();  // Move to next line after each level
    }
}

Output:

1
2 3
4 5