# Binary Tree Level Order Traversal I & II

Given a binary tree, return thelevel ordertraversal 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]
]
``````

Note:

in Binary Tree Level Order Traversal II, the requirement is only different in getting the outcome as reverse order, namely bottom-up level order traversal as:

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

## Solution

#### Top-down level order traversal

##### Using Recursive - DFS
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
levelOrderHelper(root, 0, result);
return result;
}
void levelOrderHelper(TreeNode root, int depth, List<List<Integer>> result) {
if (root == null) {
return;
}
if (depth == result.size()) {
}
levelOrderHelper(root.left, depth + 1, result);
levelOrderHelper(root.right, depth + 1, result);

}
}
``````
##### Using Queue - BFS
``````public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {

if(root == null) return wrapList;

queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
}
}
return wrapList;
}
}
``````

#### Bottom-up level order traversal

##### DFS - Recursive
``````public class Solution {
public List < List < Integer >> levelOrderBottom(TreeNode root) {
List < List < Integer >> wrapList = new LinkedList < List < Integer >> ();
levelMaker(wrapList, root, 0);
return wrapList;
}

public void levelMaker(List < List < Integer >> list, TreeNode root, int level) {
if (root == null) return;
if (level >= list.size()) {
}
levelMaker(list, root.left, level + 1);
levelMaker(list, root.right, level + 1);
}
}
``````
##### BFS - Queue
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {

if(root == null) return wrapList;

queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);