## Problem

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

For example: Given binary tree [3,9,20,null,null,15,7],

```
3
/ \
9 20
/ \
15 7
```

return its level order traversal as:

```
[
[3],
[9,20],
[15,7]
]
```

## Thought Process

- This is a typical BFS problem
- Can solve it with the help of a queue
- In Python, can use collection.deque for queue

## Code

```
# Definition for a binary tree node.
from collections import deque
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def levelOrder(self, root):
# initialization
res = [[]] # a list of list
q = deque()
level = 0 # store the level info
curr = (root, level)
q.append(curr) #append both node and its level
# if the tree is empty
if root is None:
return []
# loop as long as q has element
while q:
curr = q.popleft()
node, level = curr[0], curr[1]
if level == len(res):
# level should be 1 less than the length of result
# if level equals the len of result, need to start a new array for new level
res.append([])
res[level].append(node.val)
if node.left:
q.append((node.left, level+1))
if node.right:
q.append((node.right, level+1))
return res
```

## Complexity

- Time complexity is O(n), a while loop is used
- Space complexity is also O(n), a deque is used to store node and its level info

## White Board

Below is the white board:

## Optimization

How to improve?