102. Binary Tree Level Order Traversal

At a Glance

• Topic: trees
• Pattern: BFS
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: Very High
• LeetCode: 102

Problem (one-liner)

Given the root of a binary tree, return the level order traversal of node values: each inner list is one level, left to right.

Recognition Cues

• "Level order" / "breadth-first" on a tree
• Output grouped by level
• Queue is the default mental model

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• 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 Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	result := [][]int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		levelSize := len(queue)
		levelValues := make([]int, 0, levelSize)
		for index := 0; index < levelSize; index++ {
			node := queue[0]
			queue = queue[1:]
			levelValues = append(levelValues, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		result = append(result, levelValues)
	}
	return result
}

JavaScript

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

Walkthrough

Tree: 3 / 9,20 / null,null,15,7

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

Invariant: each outer loop drains exactly one full level that was present at loop start; newly added nodes belong to the next level.

Edge Cases

• Empty tree → []
• Single node → [[val]]
• Complete vs skew only affects queue width, not algorithm

Pitfalls

• Using queue.length inside inner loop without snapshotting levelSize first (mixes levels)
• shift() on large arrays in JS is O(n) per op—use index pointer or double-ended queue in production hot paths; LeetCode sizes usually OK

Similar Problems

• 199. Binary Tree Right Side View — last node per level or right-first DFS.
• 116. Populating Next Right Pointers in Each Node — uses level structure; can use same BFS shell.
• 104. Maximum Depth of Binary Tree — depth equals number of BFS passes minus one style thinking.

Variants

• Zigzag level order → reverse every other level.
• Level-wise averages / max per level → same traversal, different aggregation.

Mind-Map Tags

#trees #bfs #level-order #queue #by-level