## Algorithm

Problem Nmae: 102. Binary Tree Level Order Traversal

Given the `root` of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

```Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
```

Example 2:

```Input: root = [1]
Output: [[1]]
```

Example 3:

```Input: root = []
Output: []
```

Constraints:

• The number of nodes in the tree is in the range `[0, 2000]`.
• `-1000 <= Node.val <= 1000`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
struct TreeNode **q;
int n;
int sz;
} q_t;

void add2q(q_t *q, struct TreeNode *node) {
if (q->n == q->sz) {
q->sz *= 2;
q->q = realloc(q->q, q->sz * sizeof(struct TreeNode *));
//assert(q->q);
}
q->q[q->n ++] = node;
}

int depth(struct TreeNode *node) {
int l, r;
if (!node) return 0;
l = depth(node->left)  + 1;
r = depth(node->right) + 1;
if (l > r) return l;
return r;
}
void bfs(int **p, q_t *q1, q_t *q2, int *c, int d) {
int *buff, buffsz, i;
struct TreeNode *node;

if (!q1->n) return;

buffsz = 10;
buff = malloc(buffsz * sizeof(int));

for (i = 0; i  <  q1->n; i ++) {
node = q1->q[i];
//printf("%d, ", node->val);
if (c[d] >= buffsz) {
buffsz *= 2;
buff = realloc(buff, buffsz * sizeof(int));
//assert(buff);
}
buff[c[d]] = node->val;
c[d] ++;

}
//printf("done!\n");

p[d] = buff;

q1->n = 0;
bfs(p, q2, q1, c, d + 1);
}
int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
int d;
int **p, *c;
q_t q1 = { 0 }, q2 = { 0 };

*returnSize = 0;
if (!root) return NULL;

d = depth(root);
p = malloc(d * sizeof(int *));
c = calloc(d, sizeof(int));
//assert(p && c);

q1.sz = q2.sz = 10;
q1.q = malloc(q1.sz * sizeof(struct TreeNode *));
q2.q = malloc(q2.sz * sizeof(struct TreeNode *));
//assert(q1.q && q2.q);

bfs(p, &q1, &q2, c, 0);

*returnSize = d;
*columnSizes = c;

free(q1.q);
free(q2.q);

return p;
}
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

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

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector < vector<int>>res;
if(!root) return res;
deque < TreeNode*>cur;
dequenext;
cur.push_back(root);
int level = 0;
res.push_back(vector<int>());
while(!cur.empty()){
TreeNode* node = cur.front();
cur.pop_front();
if(node->left) next.push_back(node->left);
if(node->right) next.push_back(node->right);
res[level].push_back(node->val);
if(cur.empty() && !next.empty()){
res.push_back(vector<int>());
level++;
swap(cur, next);
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

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

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
}
List < List();
while (!queue.isEmpty()) {
int size = queue.size();
List < Integer> currLevel = new ArrayList<>();
while (size-- > 0) {
TreeNode removed = queue.remove();
if (removed.left != null) {
}
if (removed.right != null) {
}
}
}
return result;
}
}
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[[1]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const levelOrder = function(root) {
const res = [];
if (root == null) return res;
let next = [root];
while (next.length > 0) {
next = tr(res, next);
}
return res;
};

function tr(res, nodeArr) {
const arr = [];
const nextLevelNodes = [];
for (let i = 0; i  <  nodeArr.length; i++) {
arr.push(nodeArr[i].val);
if (nodeArr[i].left) {
nextLevelNodes.push(nodeArr[i].left);
}
if (nodeArr[i].right) {
nextLevelNodes.push(nodeArr[i].right);
}
}
if (arr.length) res.push(arr);
return nextLevelNodes;
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
q, res = [root], []
while any(q):
res.append([i.val for i in q])
q = [kid for node in q for kid in (node.left, node.right) if kid]
return res
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

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