import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class GenericTree {
    private class Node {
        int data;
        ArrayList<Node> child = new ArrayList<>();
    }

    private Node root;
    private int size;

    /*
    A generic tree is a tree which can have as many children as it can be
    It might be possible that every node present is directly connected to
    root node.

    In this code
    Every function has two copies: one function is helper function which can be called from
    main and from that function a private function is called which will do the actual work.
    I have done this, while calling from main one have to give minimum parameters.

    */
    public GenericTree() {     //Constructor
        Scanner scn = new Scanner(System.in);
        root = create_treeG(null, 0, scn);
    }

    private Node create_treeG(Node node, int childindx, Scanner scn) {
        // display
        if (node == null) {
            System.out.println("Enter root's data");
        } else {
            System.out.println("Enter data of parent of index " + node.data + " " + childindx);
        }
        // input
        node = new Node();
        node.data = scn.nextInt();
        System.out.println("number of children");
        int number = scn.nextInt();
        for (int i = 0; i < number; i++) {
            Node childd = create_treeG(node, i, scn);
            size++;
            node.child.add(childd);
        }
        return node;
    }

    /*
    Function to display the generic tree
    */
    public void display() {  //Helper function
        display_1(root);
        return;
    }

    private void display_1(Node parent) {
        System.out.print(parent.data + "=>");
        for (int i = 0; i < parent.child.size(); i++) {
            System.out.print(parent.child.get(i).data + " ");
        }
        System.out.println(".");
        for (int i = 0; i < parent.child.size(); i++) {
            display_1(parent.child.get(i));
        }
        return;
    }

    /*
     One call store the size directly but if you are asked compute size this function to calcuate
     size goes as follows
     */

    public int size2call() {
        return size2(root);
    }

    public int size2(Node roott) {
        int sz = 0;
        for (int i = 0; i < roott.child.size(); i++) {
            sz += size2(roott.child.get(i));
        }
        return sz + 1;
    }

    /*
    Function to compute maximum value in the generic tree
    */
    public int maxcall() {
        int maxi = root.data;
        return max(root, maxi);
    }

    private int max(Node roott, int maxi) {
        if (maxi < roott.data)
            maxi = roott.data;
        for (int i = 0; i < roott.child.size(); i++) {
            maxi = max(roott.child.get(i), maxi);
        }

        return maxi;
    }

    /*
    Function to compute HEIGHT of the generic tree
    */

    public int heightcall() {
        return height(root) - 1;
    }

    private int height(Node node) {
        int h = 0;
        for (int i = 0; i < node.child.size(); i++) {
            int k = height(node.child.get(i));
            if (k > h)
                h = k;
        }
        return h + 1;
    }

    /*
    Function to find whether a number is present in the generic tree or not
    */

    public boolean findcall(int info) {
        return find(root, info);
    }

    private boolean find(Node node, int info) {
        if (node.data == info)
            return true;
        for (int i = 0; i < node.child.size(); i++) {
            if (find(node.child.get(i), info))
                return true;
        }
        return false;
    }

    /*
    Function to calculate depth of generic tree
    */
    public void depthcaller(int dep) {
        depth(root, dep);
    }

    public void depth(Node node, int dep) {
        if (dep == 0) {
            System.out.println(node.data);
            return;
        }
        for (int i = 0; i < node.child.size(); i++)
            depth(node.child.get(i), dep - 1);
        return;
    }

    /*
    Function to print generic tree in pre-order
    */
    public void preordercall() {
        preorder(root);
        System.out.println(".");
    }

    private void preorder(Node node) {
        System.out.print(node.data + " ");
        for (int i = 0; i < node.child.size(); i++)
            preorder(node.child.get(i));
    }

    /*
    Function to print generic tree in post-order
    */
    public void postordercall() {
        postorder(root);
        System.out.println(".");
    }

    private void postorder(Node node) {
        for (int i = 0; i < node.child.size(); i++)
            postorder(node.child.get(i));
        System.out.print(node.data + " ");
    }

    /*
    Function to print generic tree in level-order
    */

    public void levelorder() {
        LinkedList<Node> q = new LinkedList<>();
        q.addLast(root);
        while (!q.isEmpty()) {
            int k = q.getFirst().data;
            System.out.print(k + " ");

            for (int i = 0; i < q.getFirst().child.size(); i++) {
                q.addLast(q.getFirst().child.get(i));
            }
            q.removeFirst();
        }
        System.out.println(".");
    }

    /*
     Function to remove all leaves of generic tree
     */
    public void removeleavescall() {
        removeleaves(root);
    }

    private void removeleaves(Node node) {
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < node.child.size(); i++) {
            if (node.child.get(i).child.size() == 0) {
                arr.add(i);
                // node.child.remove(i);
                // i--;
            } else
                removeleaves(node.child.get(i));
        }
        for (int i = arr.size() - 1; i >= 0; i--) {
            node.child.remove(arr.get(i) + 0);
        }
    }