22. Binary Tree Level Order Traversal

Difficulty:MediumPattern:Queue BFS Level-OrderTime:O(n)Space:O(w)

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

How It Works & Algorithmic Design

Solves using Breadth-First Search (BFS) with Queue:

Queue Setup: Initialize a FIFO queue queue = [root].
Level Loop: While queue is not empty:
- Get levelSize = queue.length.
- Create currentLevel = [].
- Loop levelSize times:
  - Dequeue node = queue.shift().
  - Add node.val to currentLevel.
  - Push non-null node.left and node.right to queue.
- Push currentLevel to result.
Return: result contains level-by-level array values.

Why This Approach Works Best

Queue FIFO processing guarantees nodes are visited strictly level by level in $O(n)$ time and $O(w)$ space (where $w$ is maximum tree width).

Example Walkthrough

Input Tree: [3, 9, 20, null, null, 15, 7]

Binary tree root.

Output Levels: [[3], [9, 20], [15, 7]]

Nodes grouped by level.

Answer: Binary Tree BFS Level Order Traversal

function levelOrder(root) {
  if (!root) return [];
  const res = [], queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(currentLevel);
  }
  return res;
}

💡 Use a FIFO queue to process tree nodes level by level.

Key Takeaways

Lock levelSize = queue.length before processing nodes in a level.
Queue FIFO order guarantees left-to-right level traversal.
Linear time complexity $O(n)$ and $O(w)$ space.