# 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],

Example:

3 / \ 9 20 / \ 15 7

return its level order traversal as:

[ , [9,20], [15,7] ]

# White Board

Below is the white board:

# Code

class ListQueue:
# implement Queue based on List
def __init__(self):
self.array = []
self.tail = 0

def __len__(self):

def push(self, value):
self.array[self.tail] = value
self.tail += 1

def pop(self):
return value

# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def levelOrder(self, root):
res = []

if root is None:
# if the tree is empty
return res

lq = ListQueue()
# initialize list queue

lq.push((root, 0))
# (the node, the level)

while lq is not None:
lq.pop()

if level == len(res):
res.append([])

res[level].append(curr_node.value)

if curr_node.left:
lq.push((curr_node.left, level + 1))

if curr_node.right:
lq.push((curr_node.right, level + 1))

return res



# Complexity

• Time complexity is O(n*m)
• used additional ds to creat stack

# Optimization

Will try to figure out a recursive solution in the future.