Binary Tree Level Order Traversal

Given a binary tree root, return the level order traversal of it as a nested list, where each sublist contains the values of nodes at a particular level in the tree, from left to right.

Approach

Use breadth-first search with a queue. For each level, process exactly the current queue size, collecting node values and enqueueing their children. This naturally groups nodes by level and handles empty trees.

Why It Works

BFS visits nodes in increasing depth order. By processing the queue in fixed-size layers, we collect exactly the nodes from one level before moving to the next, producing the required nested list structure.

Complexity

• Time: O(n)
• Space: O(n)

Reference Implementation (Python)

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