This post is completed by 1 user

  • 0
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.


Linked Lists of all the nodes at each depth 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();
			levelNodes = q.size();
			ListNode head = null;
			ListNode curr = null;
				Node n = (Node)q.remove();
				ListNode ln = new ListNode(;
					head = ln;
					curr = ln;
				}else{ = ln;
					curr =;
				if(n.left!=null) q.add(n.left);
				if(n.right!=null) q.add(n.right);

  • 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)
Linked Lists of all the nodes at each depth - Implement

Similar problem: Print binary tree, each level in one line