Binary Tree Level Order Traversal

Given the root of a binary tree, return the level-order traversal of its nodes' values — the values grouped level by level, from left to right, top to bottom.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Breadth-first traversal visits nodes level by level — reach for a queue.

Snapshot the queue's size before draining a level so you know exactly how many nodes belong to it.

Enqueue left before right to keep each level in left-to-right order.

Common doubts

It marks the boundary of the current level; if you read the size after enqueuing children, you'd merge two levels into one row.

Yes — recurse with a depth argument and append each value to res[depth]; recursing left-before-right keeps rows left-to-right.

An empty list [], not [[]] — there are no levels at all.

Interview follow-ups

· What an interviewer asks next.

Build the same list top-down, then reverse it (LeetCode 107).

Alternate the direction of each row — reverse every other level (LeetCode 103).

Fun facts

Level-order traversal is breadth-first search applied to a tree; the same queue mechanics power shortest-path BFS on graphs.
The queue never holds more than two adjacent levels at once, which bounds its size by the tree's maximum width.

Asked at

AmazonMicrosoftFacebookGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]
Level 0 is [3], level 1 is [9, 20], level 2 is [15, 7].

Example 2

Input: root = [1]
Output: [[1]]
A single node forms one level.

Example 3

Input: root = []
Output: []
An empty tree has no levels.

Constraints

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

Level-order (breadth-first) visits the tree one level at a time, left to right. The natural tool is a queue: process the nodes currently in it as one level, collecting their values while enqueuing their children for the next level.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary tree. Nodes with a value and up to two children (left, right).

Queue (FIFO). First-in-first-out — processes nodes in the order they were discovered, i.e. by level.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Output shape

“Grouped by level or one flat list?”

Grouped: return a list per level, each left-to-right.

“What about an empty tree?”

Return an empty list.

The ideal opening — say it like this

Level-order is breadth-first, so I use a queue and process it one level at a time.

At each step I snapshot how many nodes are in the queue — that's the current level — pop exactly that many, collect their values, and enqueue their children.

Understand the problem

Worked example — tree [3, 9, 20, null, null, 15, 7]

        3
       / \
      9   20
         /  \
        15   7
level 0: [3]
level 1: [9, 20]
level 2: [15, 7]
result: [[3], [9, 20], [15, 7]]

Key observations

1Aha

Snapshot the level width

Recording len(queue) before the inner loop separates one level from the next without any per-node depth bookkeeping.

2Aha

Children enqueued in order stay left-to-right

Enqueue left before right, and each level naturally comes out in left-to-right order.

3Aha

Linear time, linear space

Each node is enqueued/dequeued once (O(n)); the queue holds at most one level, up to O(n) for the widest level.

Brute force vs optimal

	BFS with a queue	DFS with a depth index
Idea	Process the queue one level at a time	Recurse, appending each value to res[depth]
Time	O(n)	O(n)
Space	O(n) queue	O(height) recursion

Both are O(n); BFS is the canonical level-order, DFS-by-depth is a neat alternative. Full code is in the Approaches selector below.

Summary

Key takeaway

Level-order = breadth-first with a queue. Snapshot the queue size to bound each level, pop that many nodes into a row, and enqueue their children. O(n) time and space.

levelOrder(root):
    q = [root]; res = []
    while q not empty:
        row = []
        for _ in range(len(q)):
            node = q.pop_front()
            row.append(node.val)
            enqueue node's children
        res.append(row)