Hard

# 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