# Converting Binary Tree to LinkedLists

The problem statement is :

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists).

My Algorithm is to use 2 Queues and BFS to accomplish this. The code is a bit involved and I've tried to make it as simple and interesting as possible. You can easily follow it reading the comments.

//LinkListNode which will be used to create linkedlists
T data;

this.data = data;
}
}

}else{
while(temp.next!=null){
temp = temp.next;
}
}
}

//return true if the list is empty
public boolean isEmpty(){
}

//i.e. first Node in the list(Like functionality
//of Queue)
public T poll(){
return data;
}

public void printList(){
System.out.println("Null List");
return;
}
while(temp.next!=null){
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println(temp.data);
}
}

}
}

}else if(currentPointer==null){
}else{
}
}

for(int i : data){
}
}

//Increments the currentPointer
public void nextCollector(){
currentPointer = currentPointer.nextCollector;
}

public void printListCollector(){

while(tempNode!=null){
System.out.println();
tempNode = tempNode.nextCollector;
}
}
}

//TreeNode to build a Tree
private static class TreeNode<T>{
T data;
TreeNode<T> left;
TreeNode<T> right;

public TreeNode(T data){
this.data = data;
}
}

static class Tree<T>{
TreeNode<T> root;

//Used for inorder traversal of Tree
public void inorder(TreeNode<T> root){
if(root.left!=null)
inorder(root.left);
System.out.print(root.data + " ");
if(root.right!=null)
inorder(root.right);
}
}

//1.Converts the Tree to LinkedLists depending on depth.
//defined previously.
//3.Uses BFS to traverse through the tree.
//4.Uses two Queues(Simulated using LinkedList) to differentiate
//between successive levels.
public static void convertToList(Tree myTree){
currentList = two;
otherList = one;
while(true){
if(currentList==one) currentList = two;
else if(currentList==two) currentList = one;

if(otherList==one) otherList=two;
else if(otherList==two) otherList=one;

while(!currentList.isEmpty()){
TreeNode curr = currentList.poll();
if(curr.left!=null)
if(curr.right!=null)
}

if(one.isEmpty() && two.isEmpty()){
break;
}
myCollector.nextCollector();
}
myCollector.printListCollector();
}

//Main method to test the program
public static void main(String[] args) {
Tree myTree = new Tree();
myTree.root = new TreeNode(1);
myTree.root.left = new TreeNode(2);
myTree.root.right = new TreeNode(3);
myTree.root.left.left = new TreeNode(4);
myTree.root.left.right = new TreeNode(5);
myTree.root.right.right = new TreeNode(7);
myTree.root.right.left = new TreeNode(6);
convertToList(myTree);
}


• The second queue is not necessary. Since the queue contains only legitimate nodes, you may use null to signal end-of-level condition:

    queue.add(root);

while (!queue.empty()) {
TreeNode curr = queue.poll();
if (curr != null) {
if (curr.left != null)
if (curr.right != null)

• By poll you mean pull, right?