102. Binary Tree Level Order Traversal

Reformulated question¶

Return the values of a binary tree grouped by depth, from top to bottom and left to right.

Example:

input tree:  [3, 9, 20, null, null, 15, 7]
output:      [[3], [9, 20], [15, 7]]
meaning:     level 0 -> [3], level 1 -> [9, 20], level 2 -> [15, 7]

Key trick¶

Use BFS level by level.

Keep a queue of nodes for the current frontier.
For each round, process exactly the current queue size.
Those processed nodes form one output level.

Trap¶

Common mistakes:

Mixing levels by not fixing the number of nodes to process before expanding children.
Forgetting the empty tree case.
Using pop(0) on a list, which makes BFS unnecessarily slow.
In tests, building a tree from LeetCode array format incorrectly when null values exist.

Why this question is interesting¶

It checks whether you recognize BFS naturally on trees.

It is also a clean example of turning traversal order into grouped output instead of a flat list.

Solve the problem with idiomatic Python¶

from utils import TreeNode, tree_build
from typing import Optional
from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        # Empty tree.
        if not root:
            return []

        result = []
        queue = deque([root])

        # BFS: one loop iteration per level.
        while queue:
            level = []

            # Freeze current level size so children go to the next level.
            for _ in range(len(queue)):
                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

collections.deque is the standard exact-fit tool here, because left pops are \(O(1)\).

Pytest test¶

from utils import tree_build
import pytest

@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([], []),
        ([1], [[1]]),
        ([3, 9, 20, None, None, 15, 7], [[3], [9, 20], [15, 7]]),
        ([1, 2, 3, 4, 5, 6, 7], [[1], [2, 3], [4, 5, 6, 7]]),
        ([1, 2, None, 3, None, None, None, 4], [[1], [2], [3], [4]]),
        ([1, None, 2, None, None, 3, None], [[1], [2], [3]]),
    ],
)
def test_level_order(values, expected):
    root = tree_build(values)
    assert Solution().levelOrder(root) == expected

Comment my solution¶

Your solution is correct and interview-acceptable.

Small improvements:

Use deque instead of lists for BFS queue behavior.
Avoid seeding levels with [[root.val]]; it is simpler to append each level inside the loop.

from utils import TreeNode, tree_build
from typing import Optional
import pytest

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        if root is None:
            return []

        level = [root]
        levels = [[root.val]]

        while level:
            next_level = []
            for node in level:
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            level = next_level
            if level:
                levels.append([node.val for node in level])
        return levels


@pytest.mark.parametrize(
    ("values", "levels"),
    [
        ([3,9,20,None,None,15,7], [[3],[9,20],[15,7]]),
        ([1], [[1]]),
        ([], [])
    ]
)
def test_levelOrder(values, levels):
    root = tree_build(values)
    assert Solution().levelOrder(root) == levels