Trees & BFS

Java Binary Tree Level Order Traversal (BFS)

Traverse a binary tree level by level using Breadth-First Search (BFS) with an ArrayDeque queue in Java.

Java Source Code

Editable code sample with line numbers

Java

import java.util.*;

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

public class Main {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

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

while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

for (int i = 0; i < levelSize; i++) {
                TreeNode current = queue.poll();
                currentLevel.add(current.val);

if (current.left != null) queue.offer(current.left);
                if (current.right != null) queue.offer(current.right);
            }
            result.add(currentLevel);
        }
        return result;
    }

public static void main(String[] args) {
        // Construct Binary Tree: [3, 9, 20, null, null, 15, 7]
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

List<List<Integer>> levels = levelOrder(root);
        System.out.println("Binary Tree Level Order Traversal:");
        for (int i = 0; i < levels.size(); i++) {
            System.out.println("  Level " + i + ": " + levels.get(i));
        }
    }
}

Expected Output

When this program is compiled and executed, the terminal outputs:

Binary Tree Level Order Traversal:
  Level 0: [3]
  Level 1: [9, 20]
  Level 2: [15, 7]

How the Code Works

Level order traversal uses a FIFO queue. At each level iteration, snapshotting queue.size() allows processing all nodes belonging to the current horizontal tier before moving down.

Time Complexity

O(N)

Space Complexity

O(N) for queue buffer

Key Takeaways & Best Practices

ArrayDeque is faster than LinkedList for Queue operations in Java.
Snapshotting levelSize inside the while loop keeps level groupings distinct.

Master Java with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.

Related Java Examples

Trees & Recursion

O(N)

Java Invert / Mirror Binary Tree

Invert a binary tree by recursively swapping left and right child pointers.

Runnable Code

View Code

Data Structures & Algorithms

O(N) single-pass lookup

Java Two Sum Problem (Optimized One-Pass HashMap)

Find two indices in an array of integers that add up to a specific target number using a single-pass HashMap in O(n) time.

Java Program to Reverse a String (StringBuilder & Two Pointers)

Reverse strings in Java efficiently using StringBuilder and in-place char array two-pointer swapping.

Runnable Code

View Code

How the Code Works

Level order traversal uses a FIFO queue. At each level iteration, snapshotting queue.size() allows processing all nodes belonging to the current horizontal tier before moving down.

Time Complexity

O(N)

Space Complexity

O(N) for queue buffer

Key Takeaways & Best Practices

ArrayDeque is faster than LinkedList for Queue operations in Java.
Snapshotting levelSize inside the while loop keeps level groupings distinct.

Java Binary Tree Level Order Traversal (BFS)

Java Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master Java with ZenCompiler

Related Java Examples

Java Invert / Mirror Binary Tree

Java Two Sum Problem (Optimized One-Pass HashMap)

Java Program to Reverse a String (StringBuilder & Two Pointers)

Platform & Tools

Account

Company & Help

Legal & Policies

Java Binary Tree Level Order Traversal (BFS)

Java Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master Java with ZenCompiler

Related Java Examples

Java Invert / Mirror Binary Tree

Java Two Sum Problem (Optimized One-Pass HashMap)

Java Program to Reverse a String (StringBuilder & Two Pointers)