# 102. Binary Tree Level Order Traversal

## 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:

How to improve?