Output: K linked lists if the height of tree is k. Each linked list will have all the nodes of each level.

Example:

Approach:

Recursion:

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. add these to a linked list

After this while loop put a line break and create a new linked list

ArrayList al = new ArrayList();
while(!q.isEmpty()){
levelNodes = q.size();
ListNode head = null;
ListNode curr = null;
while(levelNodes>0){
Node n = (Node)q.remove();
ListNode ln = new ListNode(n.data);
if(head==null){
head = ln;
curr = ln;
}else{
curr.next = ln;
curr = curr.next;
}
if(n.left!=null) q.add(n.left);
if(n.right!=null) q.add(n.right);
levelNodes--;
}
al.add(head);
}

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

Time Complexity : O(N)

Complete Code:

Output:

->5
->10->15
->20->25->30->35

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Pingback: Level Order Traversal, Print each level in separate line. | Algorithm Tutorials()