// D. Scott
// CCI - Problem 4.3
// Create a series of linked lists containing nodes at each depth level
// of a given binary tree

import java.util.LinkedList;

class Node {
    int data;
    Node[] children;
    
    public Node(int d) {
        data = d;
    }
    
    void setChildren(Node a, Node b) {
        this.children = new Node[2];
        this.children[0] = a;
        this.children[1] = b;
    }
}

public static void main (String[] args)
{
    // Generate binary tree
    Node root = new Node(8);
    Node n1 = new Node(42);
    Node n2 = new Node(12);
    root.setChildren(n1,n2);
    Node n3 = new Node(15);
    Node n4 = new Node(3);
    n1.setChildren(n3,n4);
    Node n5 = new Node(23);
    Node n6 = new Node(35);
    n2.setChildren(n5,n6);
    Node n7 = new Node(61);
    Node n8 = new Node(84);
    n3.setChildren(n7,n8);
    Node n9 = new Node(9);
    Node n10 = new Node(7);
    n4.setChildren(n9,n10);
    Node n11 = new Node(6);
    Node n12 = new Node(111);
    n5.setChildren(n11,n12);
    Node n13 = new Node(82);
    Node n14 = new Node(2);
    n6.setChildren(n13,n14);

    // depth of tree
    int d = 4;
    
    // create a list to store lists of each depth level's nodes
    LinkedList<LinkedList<Node>> allDepthLevels = new LinkedList<>();
    
    
    LinkedList<Node> rootList = new LinkedList<>();
    rootList.addLast(root);
    
    // add root from depth 0
    allDepthLevels.addLast(rootList);

    // get each subsequent depth level's nodes and add to list
    for (int i = 1; i < d; i++) {
        rootList = listNodes(rootList);
        allDepthLevels.addLast(rootList);
    }
    
    // print nodes from each depth level
    for (int i = 0; i < allDepthLevels.size(); i++) {
        System.out.println("Depth "+ i + ":");
        LinkedList<Node> depth = allDepthLevels.get(i);
        for (int j = 0; j < depth.size(); j++) {
            Node n = depth.get(j);
            System.out.print(n.data+"  ");
        }
        System.out.println("\n");
    }
}

// function to retrieve all nodes from a given depth level
LinkedList<Node> listNodes(LinkedList<Node> n) {
    LinkedList<Node> d = new LinkedList<>();
    int size = n.size();
    // process all nodes at previous depth
    for (int i = 0; i < size; i++) {
        Node nx = n.get(i);
        // Get all of their children and add to a list
        for (int j = 0; j < nx.children.length; j++) {
            d.addLast(nx.children[j]);
        }
    }
    return d;   

}