Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Approach: Breadth-First Search with Queue (Optimal Solution)

Algorithm

1. If the root is null, return an empty list
2. Use a queue initialized with the root node
3. While the queue is not empty:
   • Record the current queue size n — the number of nodes at this level
   • Poll n nodes, collect their values into a level list, and enqueue their children
   • Append the level list to the result
4. Return the result

Key Insight

Capturing n = queue.size() at the start of each iteration is what separates one level from the next. All nodes enqueued during the current level’s processing belong to the next level, so processing exactly n nodes per iteration guarantees correct level boundaries.

Time & Space Complexity

• Time Complexity: O(n) - every node is visited once
• Space Complexity: O(n) - the queue holds at most one level of nodes (O(n) in the worst case)

Java Implementation

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class BinaryTreeLevelOrderTraversal {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int n = queue.size(); n > 0; n--) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}

Example Walkthrough

For root = [3,9,20,null,null,15,7]:

1. queue=[3], process 3 → level=[3], enqueue 9,20. ans=[[3]]
2. queue=[9,20], process 9 → level=[9], process 20 → level=[9,20], enqueue 15,7. ans=[[3],[9,20]]
3. queue=[15,7], process 15 → level=[15], process 7 → level=[15,7]. ans=[[3],[9,20],[15,7]]

Alternative Approach: Recursive DFS with Level Tracking

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeLevelOrderDFS {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }

    private void dfs(TreeNode root, int depth, List<List<Integer>> ans) {
        if (root == null) {
            return;
        }
        if (ans.size() == depth) {
            ans.add(new ArrayList<>());
        }
        ans.get(depth).add(root.val);
        dfs(root.left, depth + 1, ans);
        dfs(root.right, depth + 1, ans);
    }
}

The recursive variant appends each node to the list for its depth. It produces the same result but relies on the recursion stack instead of an explicit queue.

Key Insights

1. Level Size Snapshot: queue.size() captured before processing defines the current level
2. FIFO Order: The queue guarantees left-to-right order within each level
3. Empty Tree: Returning an empty list (not a list with an empty list) handles the null root
4. Visits Each Node Once: Both BFS and DFS approaches run in O(n) time

The BFS queue approach is the optimal solution, providing O(n) time and O(n) space.