102. Binary Tree Level Order Traversal

At a Glance

• Topic: Tree
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 102

Problem Statement

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 & Solution Steps

• Brute force — O(n²) — repeated depth scans for each level height (terrible).
• Better — BFS with sentinel # between levels — O(n) time / O(w) space — works but clunky.
• Optimal — O(n) time / O(w) queue space — process queue in chunks: levelSize = len(queue) each outer iteration.

Optimal JS Solution

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

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

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.