This post is completed by 1 user

Add to List 
40. In a Binary Tree, Create Linked Lists of all the nodes at each depth
Objective: Given a Binary tree create Linked Lists of all the nodes at each depth, say if the tree has height k then create k linked lists.
Example:
Approach  Recursion:
 Initialize a list, this will store all the linked lists.
 Do the level order traversal (Breadth First Search).
 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 as levelNodes.
 Now while levelNodes>0,
 Take out the node from the queue.
 Add it to the linked list
 Add the children of that node into the queue
 After this while loop put a line break and create a new linked list
 See the code below and the Image for a better understanding
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)
>5 >10>15 >20>25>30>35
Similar problem: Print binary tree, each level in one line