Level Order Traversal¶

Problem¶

Given the root of a binary tree, return the level-order traversal as a list of lists, where each inner list contains the values at that depth level.

Approach¶

BFS with a deque. Process one level at a time by iterating over the current queue length, appending children for the next level.

When to Use¶

BFS on trees — "level order", "zigzag order", "right side view", any problem requiring per-level processing. Also: shortest-path-like queries on trees, hierarchical data serialization.

Complexity¶


Time	`O(n)`
Space	`O(w) where w = max width of the tree (up to n/2)`

Implementation¶

SolutionTestsChallenge

level_order_traversal ¶

Level-order (BFS) traversal of a binary tree.

Problem

Given the root of a binary tree, return the level-order traversal as a list of lists, where each inner list contains the values at that depth level.

Approach

BFS with a deque. Process one level at a time by iterating over the current queue length, appending children for the next level.

When to use

BFS on trees — "level order", "zigzag order", "right side view", any problem requiring per-level processing. Also: shortest-path-like queries on trees, hierarchical data serialization.

Complexity

Time: O(n) Space: O(w) where w = max width of the tree (up to n/2)

level_order ¶

level_order(root: TreeNode | None) -> list[list[int]]

Return level-order traversal as a list of lists.

level_order(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))) [[3], [9, 20], [15, 7]]

Source code in src/algo/trees/level_order_traversal.py

def level_order(root: TreeNode | None) -> list[list[int]]:
    """Return level-order traversal as a list of lists.

    >>> level_order(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7))))
    [[3], [9, 20], [15, 7]]
    """
    if not root:
        return []

    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        level: list[int] = []
        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

tests/trees/test_level_order_traversal.py

"""Tests for level-order traversal."""

from algo.trees.level_order_traversal import TreeNode, level_order


class TestLevelOrder:
    def test_basic(self) -> None:
        tree = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
        assert level_order(tree) == [[3], [9, 20], [15, 7]]

    def test_empty_tree(self) -> None:
        assert level_order(None) == []

    def test_single_node(self) -> None:
        assert level_order(TreeNode(1)) == [[1]]

    def test_left_skewed(self) -> None:
        tree = TreeNode(1, TreeNode(2, TreeNode(3)))
        assert level_order(tree) == [[1], [2], [3]]

    def test_complete_tree(self) -> None:
        tree = TreeNode(
            1,
            TreeNode(2, TreeNode(4), TreeNode(5)),
            TreeNode(3, TreeNode(6), TreeNode(7)),
        )
        assert level_order(tree) == [[1], [2, 3], [4, 5, 6, 7]]

    def test_sparse_tree(self) -> None:
        """Tree with missing children at various levels."""
        tree = TreeNode(1, None, TreeNode(3, TreeNode(5), None))
        assert level_order(tree) == [[1], [3], [5]]

Implement it yourself

Run: just challenge trees level_order_traversal

Then implement the functions to make all tests pass. Use just study trees for watch mode.

Reveal Solution

level_order_traversal ¶

Level-order (BFS) traversal of a binary tree.

Problem

Given the root of a binary tree, return the level-order traversal as a list of lists, where each inner list contains the values at that depth level.

Approach

BFS with a deque. Process one level at a time by iterating over the current queue length, appending children for the next level.

When to use

BFS on trees — "level order", "zigzag order", "right side view", any problem requiring per-level processing. Also: shortest-path-like queries on trees, hierarchical data serialization.

Complexity

Time: O(n) Space: O(w) where w = max width of the tree (up to n/2)

level_order ¶

level_order(root: TreeNode | None) -> list[list[int]]

Return level-order traversal as a list of lists.

level_order(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))) [[3], [9, 20], [15, 7]]

Source code in src/algo/trees/level_order_traversal.py

def level_order(root: TreeNode | None) -> list[list[int]]:
    """Return level-order traversal as a list of lists.

    >>> level_order(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7))))
    [[3], [9, 20], [15, 7]]
    """
    if not root:
        return []

    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        level: list[int] = []
        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