# In a Binary Tree, Create Linked Lists of all the nodes at each depth.

Objec­tive: Given a Binary tree cre­ate Linked Lists of all the nodes at each depth , say if the tree has height k then cre­ate k linked lists.

NOTE : This prob­lem is very sim­i­lar “Print binary tree, each level in one line

Input: A binary tree

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

Exam­ple:

Linked Lists of all the nodes at each depth Example

Approach:

Recur­sion:

• Cre­ate a ArrayList of Linked List Nodes.
• Do the level order tra­ver­sal using queue(Breadth First Search). Click here to know about how to level order traversal.
• For get­ting all the nodes at each level, before you take out a node from queue, store the size of the queue in a vari­able, say you call it as levelNodes.
• Now while levelNodes>0, take out the nodes and print it and add their chil­dren into the queue. add these to a linked list
• After this while loop put a line break and cre­ate 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);
curr = ln;
}else{
curr.next = ln;
curr = curr.next;
}
levelNodes--;
}
}

• Since we had taken the queue size before we add new nodes, we will get the count at each level and after print­ing this count, put a line break, see the exam­ple below
• Time Com­plex­ity : O(N)

Linked Lists of all the nodes at each depth — Implement

Com­plete Code:

Out­put:

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