# BFS Traversal

Breadth first search, or BFS, is a common search algorithm for binary trees. In the question statement, when you see level order traversal, you should think about BFS immediately.

## List Tree Element Level by Level

When doing BFS, there are a few common patterns. They can all be pretty well summarized in the solution for the following question:

Given a binary tree, populate an array to represent level-by-level traversal. You should populate the values of all nodes of each level from left to right in separate sub-arrays.

```
from collections import deque
def traverse(root):
result = []
queue = deque()
if root:
queue.append(root)
while queue:
size = len(queue)
level = []
for _ in range(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
```