package Question4_4;

import CtCILibrary.*;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.LinkedList;

public class QuestionBFS {

public static ArrayList<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root) {

ArrayList<LinkedList<TreeNode>> result = new ArrayList<LinkedList<TreeNode>>();

/* "Visit" the root */

LinkedList<TreeNode> current = new LinkedList<TreeNode>();

if (root != null) {

current.add(root);

}

while (current.size() > 0) {

result.add(current); // Add previous level

LinkedList<TreeNode> parents = current; // Go to next level

current = new LinkedList<TreeNode>();

for (TreeNode parent : parents) {

/* Visit the children */

if (parent.left != null) {

current.add(parent.left);

}

if (parent.right != null) {

current.add(parent.right);

}

}

}

return result;

}

public static void printResult(ArrayList<LinkedList<TreeNode>> result){

int depth = 0;

for(LinkedList<TreeNode> entry : result) {

Iterator<TreeNode> i = entry.listIterator();

System.out.print("Link list at depth " + depth + ":");

while(i.hasNext()){

System.out.print(" " + ((TreeNode)i.next()).data);

}

System.out.println();

depth++;

}

}

public static void main(String[] args) {

int[] nodes_flattened = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

TreeNode root = AssortedMethods.createTreeFromArray(nodes_flattened);

ArrayList<LinkedList<TreeNode>> list = createLevelLinkedList(root);

printResult(list);

}

}