Binary Tree Level Order Traversal

Intuition

Breadth-first search naturally visits nodes in level order, but a plain queue mixes nodes from adjacent levels together. The trick to separating levels is to snapshot the queue's size at the start of each outer loop: that count is exactly how many nodes belong to the current level. We then dequeue precisely that many nodes into one group while enqueuing their children for the next round. Because children are always appended behind the current level, each snapshot cleanly captures one full level before its successors are touched.

Algorithm walkthrough

1. 1Return an empty list if the root is null; otherwise seed a queue with the root.
2. 2While the queue is not empty, read its current length and call that the level size.
3. 3Create a fresh list for this level and loop exactly level-size times.
4. 4On each iteration dequeue a node, add its value to the level list, and enqueue its non-null children.
5. 5After the inner loop, append the completed level list to the result.
6. 6When the queue empties, return the list of levels.

Implementation

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result: List[List[int]] = []
        queue: deque = deque([root])
        while queue:
            level_size = len(queue)
            level: List[int] = []
            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