Medium

# 39. Level Order Traversal, Print each level in separate line

Objective: Given a Binary tree, Print each level of a tree in a separate line.

NOTE: This problem is very similar to Create Linked Lists of all the nodes at each depth

Example:

Approach:

Naive Approach:

1. Get the height of the tree.
2. Put a for loop for each level in the tree.
3. for each level in step 2, do pre-order traversal and print only when the height matches the level.
4. Look at the code for a better explanation

Time Complexity: O(N^2) - because at each level we are traversing the entire tree.

Better Solution:   Time Complexity - O(N)

2. For getting all the nodes at each level, before you take out a node from the queue, store the size of the queue in a variable, say you call it levelNodes.
3. Now while levelNodes>0, take out the nodes print it, and add their children into the queue.
4. After this while loop put a line break.
```while(!q.isEmpty()){
levelNodes = q.size();
while(levelNodes>0){
Node n = (Node)q.remove();
System.out.print(" " + n.data);
levelNodes--;
}
System.out.println("");
}

```
• Since we had taken the queue size before we added new nodes, we will get the count at each level and after printing this count, put a line break, see the example below

```Output by Naive Approach :
5
10 15
20 25 30 35
Output by Better Approach :
5
10 15
20 25 30 35
```