This post is completed by 1 user
|
Add to List |
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:
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)
Code:
->5 ->10->15 ->20->25->30->35
Also Read: