Reference: Problem I & Problem II
Difficulty: Medium

## Problem

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

Example:

## Analysis

### Recursion (preorder)

Expand the result list if the current level is equal to the size of result list. Visiting a node involves putting its value to the corresponding array list of current level.

Time: $O(N)$
Space: $O(h + N)$ including result list.

### Iteration (BFS)

Not necessary to use one more queue to store the level information.

Time: $O(N)$
Space: $O(h + N)$ including result list.

## Problem II

Return the bottom-up level order traversal.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.