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

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

**Input:** A binary tree

**Output: Each level of binary tree, in one line **

**Example:**

**Approach:**

**Naive Approach:**

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

**Time Complexity : O(N^2) – because each level you are traversing the entire tree.**

**Better Solution : Time Complexity – O(N)**

- Create a ArrayList of Linked List Nodes.
- Do the level order traversal using queue(Breadth First Search). Click here to know about how to level order traversal.
- For getting all the nodes at each level, before you take out a node from queue, store the size of the queue in a variable, say you call it as levelNodes.
- Now while levelNodes>0, take out the nodes and print it and add their children into the queue.
- 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); if(n.left!=null) q.add(n.left); if(n.right!=null) q.add(n.right); levelNodes--; } System.out.println(""); }

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

**Complete Code:**

import java.util.LinkedList; | |

import java.util.Queue; | |

public class LevelOrderTraversal { | |

public void levelOrderNaiveApproach(Node root){ | |

int h = height(root); | |

for(int i=1;i<=h;i++){ | |

printLevels(root,i); | |

System.out.println(""); | |

} | |

} | |

public void printLevels(Node root, int h){ | |

if(root==null) return; | |

if(h==1) System.out.print(" " + root.data); | |

else{ | |

printLevels(root.left,h–1); | |

printLevels(root.right,h–1); | |

} | |

} | |

public int height(Node root){ | |

if (root==null) return 0; | |

return 1 + Math.max(height(root.left),height(root.right)); | |

} | |

public void levelOrderQueue(Node root){ | |

Queue q = new LinkedList(); | |

int levelNodes =0; | |

if(root==null) return; | |

q.add(root); | |

while(!q.isEmpty()){ | |

levelNodes = q.size(); | |

while(levelNodes>0){ | |

Node n = (Node)q.remove(); | |

System.out.print(" " + n.data); | |

if(n.left!=null) q.add(n.left); | |

if(n.right!=null) q.add(n.right); | |

levelNodes—; | |

} | |

System.out.println(""); | |

} | |

} | |

public static void main (String[] args) throws java.lang.Exception | |

{ | |

Node root = new Node(5); | |

root.left = new Node(10); | |

root.right = new Node(15); | |

root.left.left = new Node(20); | |

root.left.right = new Node(25); | |

root.right.left = new Node(30); | |

root.right.right = new Node(35); | |

LevelOrderTraversal i = new LevelOrderTraversal(); | |

System.out.println(" Output by Naive Approach : "); | |

i.levelOrderNaiveApproach(root); | |

System.out.println(" Output by Better Approach : "); | |

i.levelOrderQueue(root); | |

} | |

} | |

class Node{ | |

int data; | |

Node left; | |

Node right; | |

public Node(int data){ | |

this.data = data; | |

this.left = null; | |

this.right =null; | |

} | |

} |

**Output**:

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

Or you can take two counters, current and next level. Keep printing on the same line till current reaches 0. at that point you have completed a level. make current=next, next=0 and print a line break. this will avoid a second loop.

Did you try implementing it? what values will you store in counters and more importantly how will you know that you have reached to the last node at particular level?? you will need an identifier to insert in queue to know about the level change.

https://gist.github.com/adeydas/d209dca13927fb8a63fd – I checked with only the input in this posts, so feel free to check some more.

Thanks for the link. I have checked the code. Both has the same complexity, what you have said is right. the code will iterate the same number of time.

what is the time complexity of the better solution?

We are visiting each node only once , so it will be O(N)