This post is completed by 1 user

  • 0
 Add to List
Hard

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.

NOTE : This problem is very similar "Print binary tree, each level in one line"

Input: A binary tree

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

Example:

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

Code:


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

Also Read: