MediumTrees

Level Order Traversal

BFS level by level

Solution Approach

BFS using queue. Process nodes level by level, track level boundaries.

Implementation

def levelOrder(root):
    if not root:
        return []
    
    from collections import deque
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        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

Complexity Analysis

Time Complexity

O(V + E)

Space Complexity

O(V)

Key Learning Points

Use queue for level-order traversalMaintain visited setProcess all neighbors at current level before next