Implement binary tree level order traversal

Question

Given a binary tree, return the level order traversal of its nodes values (i.e., from left to right, level by level).

TreeTraverser · Accepted Answer

Classic BFS solution using a queue:

```python
from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []

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

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

for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

result.append(current_level)

return result
```

**Time:** O(n) - visit each node once
**Space:** O(n) - queue can hold up to n/2 nodes (last level)

1 Answer