Optimal Python Solution for Binary Tree Level Order Traversal (Interview Script)

2025-10-04

The Logic

• Nodes must be processed level by level from top to bottom.
• Breadth-first search naturally processes nodes in this order.
• A queue tracks the current level while preserving traversal order.

Implementation / Diagram

Key Invariant

At each iteration, the queue contains exactly the nodes of the current level.

from collections import deque

def levelOrder(root):
    if not root:
        return []

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

    while queue:
        level = []
        level_size = len(queue)

        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