Binary Tree Level Order Traversal

Problem

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:

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

Constraints:

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

Solution

Approach: BFS with Queue

The key insight is to use a queue for BFS, processing all nodes at each level before moving to the next.

Implementation

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> 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

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(w), where w is the maximum width of the tree (for the queue).

Key Insights

Level-by-Level Processing: We process all nodes at current level before moving to the next by using len(queue) to determine level size.
Queue for BFS: A queue naturally supports breadth-first traversal with FIFO ordering.
Level Separation: Capturing level_size at the start of each level allows us to group nodes by level.
Left to Right: Adding left child before right child ensures left-to-right ordering within each level.
BFS Pattern: This is the classic BFS pattern for trees - process current level, add children to queue for next level.