Given the root of a binary tree , return the level order traversal of the binary tree .

Level order traversal means picking nodes from left to right level by level.

For example,

For the below tree:

Level order traversal is [[3],[9,20],[15,7]]

It is a list of lists.

Each list represent the nodes at that level from left to right.

At level 0 we have only one node 3 .

At level 1 we have two nodes 9 and 20 from left to right.

At level 2 we have two nodes 15 and 7 from left to right.

Try out the solution here:

https://leetcode.com/problems/binary-tree-level-order-traversal/

## Solution:

Use DFS or BFS

**Approach 1 – Use Depth First Search**

In Depth First Search , as usual you use recursion.

Make recursive calls for both the left node and right of each node at each level.

Every recursive call should have a base condition.

In this case the base condition is checking if the node is null or not.

If it is null return .

Else start the main logic.

Have a global list named output to hold the list of nodes at each level.

Have a global variable named level to keep track of each level in the recursive call.

In the recursive call , you check the current level.

If it is equal to the output size , then the list of nodes for the current level is not already in the output list.

So create a new list of nodes and add it to the current level.

If it is not equal to output size , then that level is already in the output list , so add the current node to that list.

Below is the logic to populate the output list data structure:

```
List<Integer> nodes = new ArrayList<>();
nodes.add(node.val);
if(output.size() == level ){
output.add(nodes);
}else{
output.get(level).add(node.val);
}
```

After the above step increment the level and make recursive calls on the left and right nodes of the current node.

Here is the logic:

```
int newlevel = level +1;
traverse(node.left,newlevel);
traverse(node.right,newlevel);
```

Here is the entire code:

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<List<Integer>> output = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
traverse(root,0);
return output;
}
public void traverse(TreeNode node,int level){
if(node == null) return;
List<Integer> nodes = new ArrayList<>();
nodes.add(node.val);
if(output.size() == level ){
output.add(nodes);
}else{
output.get(level).add(node.val);
}
int newlevel = level +1;
traverse(node.left,newlevel);
traverse(node.right,newlevel);
return ;
}
}
```

**Algorithm:**

- Create two global variables : one to hold the output and one to track the current level of the tree while doing DFS
- Invoke a recursive function with the initial level 0 and the root node.
- In the recursive function do the following:
- If the node is null , return – this is the base condition.
- If it is not null , then find if the current level is already in the output list
- If it is not already present (output size == level) , then create a new list , add the current node value and add this list to the output list
- If it is already present , then add the current node value to the output list for the specific level
- Increment the level.
- Invoke the recursive call for the left node
- Invoke the recursive call for the right node
- After the recursive function , return the output.

**Time complexity:**

Since we traverse each node once time complexity is O(n)

**Space complexity:**

There is a recursive call made for each node , so size of recursion stack is O(n)

**Approach 2 – Breadth First Search**

In this case , as usual we use a queue.

Add the first node to the queue.

Then until the queue is empty do the following:

- Pop all elements in the queue and add it to the current level if it is already in the output list , else create a new list and add it to the output list
- Put the left node and the right node of each element in the current level to the queue
- Increment the level after processing all the elements in the current level.

Here is the code:

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> output = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int level = 0;
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;i++){
TreeNode node = queue.poll();
if(node == null) continue;
if(output.size() == level){
List<Integer> nodes = new ArrayList<Integer>();
nodes.add(node.val);
output.add(nodes);
}else{
output.get(level).add(node.val);
}
queue.add(node.left);
queue.add(node.right);
}
level++;
}
return output;
}
}
```

Note that at the end of every iteration of the while loop ,

We will have all the nodes of the next level of the tree in the queue.

**Algorithm:**

- Create an output list to hold the list of node values at each level of the tree
- Create a queue to do BFS
- Put the root node into the queue
- While queue is not empty do the following:
- Check queue size and then for each node in the queue do the following:
- Pop the node
- If it is null , then check the next node
- Check if the current level is present in the output list , if no create a new one , else add the current node to the current level
- Put the left node of the current node into the queue
- Put the right node of the current node into the queue
- After all the nodes of the current level are processed , increment the level
- After all the nodes in the queue are processed return the output.

**Time complexity:**

Since we traverse each node once , time complexity is O(n)

**Space complexity:**

Each node is put into the queue so we need a queue of space O(n)

That’s it!