Skip to main content

102 - Binary Tree Level Order Traversal

Difficulty: Medium | Pattern: BFS / Queue | Company tags: Amazon, Google, Facebook, Microsoft

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:

    3
   / \
  9  20
     / \
    15   7

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: []

Algorithm Flow​

Approach: BFS with Queue​

Key insight: Use a queue (FIFO). Process the queue level by level: at the start of each level, record how many nodes are currently in the queue (that's this level's size), process exactly that many nodes, and add their children for the next level.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root) -> list[list[int]]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

Dry Run​

Tree: root=3, left=9, right=20, 20.left=15, 20.right=7

Iterationqueue beforelevel_sizelevel processedqueue after
1[3]1[3][9, 20]
2[9, 20]2[9, 20][15, 7]
3[15, 7]2[15, 7][]

Result: [[3], [9, 20], [15, 7]] ✓

Key Design: Snapshot the Level Size​

The trick is level_size = len(queue) before the inner loop. This ensures we only process nodes from the current level — not nodes added to the queue as children during this iteration.

Variants​

ProblemVariation
107 - Level Order Traversal IIReturn levels bottom-up: result.reverse() at the end
103 - Zigzag Level OrderAlternate left-to-right and right-to-left per level: use a flag
637 - Average of LevelsReturn average of each level instead of all values
199 - Binary Tree Right Side ViewReturn only the last element of each level
515 - Find Largest Value in Each Tree RowReturn max of each level

Edge Cases​

  • Empty tree → []
  • Single node → [[root.val]]
  • Skewed tree (all left or all right) → n levels each with 1 element

Complexity​

  • Time: O(n) — every node is enqueued and dequeued exactly once
  • Space: O(w) where w is the maximum width of the tree; worst case O(n) for a complete tree's bottom level

Key Terms​

TermDefinition
BFS (Breadth-First Search)Traversal strategy that visits nodes level by level using a FIFO queue.
QueueFIFO data structure holding nodes waiting to be processed; children are enqueued after their parent is dequeued.
Level size snapshotCapturing len(queue) before the inner loop so only the current level's nodes are processed.
Tree widthThe maximum number of nodes at any single level, which bounds the queue's peak size.

FAQ​

Q: Can this be solved without extra space beyond the output? A: Not with a truly O(1) auxiliary approach — you need at least a queue (BFS) or a depth-tracking structure (recursive DFS) to group nodes by level; both use O(w) or O(h) extra space.

Q: What if the tree is empty? A: The initial if not root: return [] check handles it directly, returning an empty list of levels.

Q: How would you solve this recursively (DFS) instead of BFS? A: Pass the current depth into a helper; if depth == len(result), append a new list, then append node.val to result[depth], and recurse into both children.

Q: What's the difference between this and zigzag level order traversal (LC 103)? A: Same BFS skeleton, but alternate the direction each level is appended (or reverse odd-indexed levels) using a boolean flag.

Q: Why snapshot level_size = len(queue) before the inner loop instead of checking queue length inside the loop? A: Because children are appended to the same queue during the inner loop; without snapshotting the size first, the loop would incorrectly consume next-level nodes as part of the current level.

Quick Revision​

  • Use a queue and process nodes in FIFO order to guarantee left-to-right, top-to-bottom visiting.
  • Snapshot level_size = len(queue) before each inner loop — this is the key trick that separates levels.
  • For each node dequeued, record its value and enqueue its non-null children.
  • Append each completed level's values as one sub-list to the result.
  • Empty tree → return [] immediately.
  • Time: O(n), every node enqueued/dequeued once. Space: O(w), bounded by the widest level.
  • Variants swap only the per-level logic: reverse order, alternate direction, take average, take last, take max.
  • Can also be done recursively by tracking depth and appending to result[depth].
  • 107 - Binary Tree Level Order Traversal II (pattern: same BFS, reverse result at the end) — not in this directory.
  • 103 - Binary Tree Zigzag Level Order Traversal (pattern: same BFS, alternate direction per level) — not in this directory.
  • 637 - Average of Levels in Binary Tree — same BFS grouping, averages each level instead of collecting all values.
  • 199 - Binary Tree Right Side View — same BFS grouping, keeps only the last node of each level.