Level wise linkedlist

Given a binary tree, write code to create a separate linked list for each level. You need to return the array which contains head of each level linked list.

Input format :

Elements in level order form (separated by space). If any node does not have left or right child, take -1 in its place.

Output format : Each level linked list is printed in new line (elements separated by space).

Sample Input :

5 6 10 2 3 -1 -1 -1 -1 -1 9 -1 -1

Sample Output :

5 
6 10 
2 3 
9

This code is contribited bu Pushpendra

import java.util.ArrayList;

import java.util.*;

public class Solution {

/* Binary Tree Node class

* 

* class BinaryTreeNode<T> {

T data;

BinaryTreeNode<T> left;

BinaryTreeNode<T> right;

public BinaryTreeNode(T data) {

this.data = data;

}

}

*/

/* class Node<T> {

T data;

Node<T> next;

Node(T data){

this.data = data;

}

}

*/

Main Code That You have to Write


public static ArrayList<Node<BinaryTreeNode<Integer>>> LLForEachLevel(BinaryTreeNode<Integer> root) {
        
        Node<BinaryTreeNode<Integer>> head = null;
        Node<BinaryTreeNode<Integer>> tail = null;

        

        ArrayList<Node<BinaryTreeNode<Integer>>> arr = new  ArrayList<Node<BinaryTreeNode<Integer>>>();
        
        
        
        Queue<BinaryTreeNode<Integer>> pendingChild = new LinkedList<BinaryTreeNode<Integer>>();
        
         Queue<BinaryTreeNode<Integer>> q = new LinkedList<BinaryTreeNode<Integer>>();
        
        pendingChild.add(root);
        
        while(!pendingChild.isEmpty())
        {
            while(!pendingChild.isEmpty())
            {
                
                BinaryTreeNode<Integer> front = pendingChild.poll();
                
                Node<BinaryTreeNode<Integer>> node = new Node<BinaryTreeNode<Integer>>(front);//here we have maked a node with front data
                
                if(head == null)
                {
                    
                    head = node;
                    tail = node;
                }
                else{
                    tail.next = node;
                    
                    tail = tail.next;
                }
                
                //Now we will add left and right child of root into q queue
                
                if(front.left != null)
                {
                    q.add(front.left);
                }
                
                if(front.right != null)//this is for adding write chold of front
                {
                    q.add(front.right);
                    
                }
            }
            
            //Before going to second we will add thr head of link list into arrayList;
            
            arr.add(head);
            
            //now we reached into second line
            
            head =null;
            tail = null;
            
              Queue<BinaryTreeNode<Integer>> temp = new LinkedList<BinaryTreeNode<Integer>>();
            
            temp = pendingChild;
            
            pendingChild = q;
            
            q = temp;
            
            
        }
        
        return arr;
        
        



}


}