Full lesson preview

Compute level order traversal

Return the nodes of a binary tree level-by-level (breadth-first).

Python practice15 minTrees & Binary TreesIntermediateLast updated March 29, 2026

Problem statement

Given the root of a binary tree, return its level order traversal as a list of lists. Each inner list should contain the values of nodes at that tree level, from left to right. If the tree is empty, return an empty list. Implement level_order(root) -> List[List[int]].

Task

Implement level-order traversal that returns a list of lists of node values, each inner list representing a level from top to bottom.

Examples

Two-level tree

Input

level_order(TreeNode(1, TreeNode(2), TreeNode(3)))

Output

[[1], [2, 3]]

Level 0 has [1], level 1 has [2,3].

Input format

A single argument: root (TreeNode or None).

Output format

A list of lists of integers representing node values per level.

Constraints

- Use O(n) time and O(n) extra space for the queue. - Tree size up to a few thousand nodes.

Samples

Sample 1

Input

level_order(None)

Output

[]

Empty tree returns an empty list.