/*
     * CTM = CTP = theta(n) serve visitare l'intero albero
     * CSM = theta(log(n)) albero bilanciato
     * CSP = theta(n) albero degenere
     */
    public static int countSubtrees(AlberoBin<Integer> a){
        int[] cont = new int[1];
        countSubtrees(a, cont);
        return cont[0];
    }


    // The function returns the value of the root node if all nodes in subtree
    // rooted at root have same values, else it returns infinity
    // Here count stores the result and it is passed by reference
    private static int countSubtrees(AlberoBin<Integer> a, int[] cont) {
        // base case: empty tree
        if (a == null)
            return Integer.MAX_VALUE;
        // if root is a leaf node, increase the count and return root node data
        if (a.sin() == null && a.des() == null) {
            cont[0]++;
            return a.val();
        }
        // recurse for left subtree and right subtree
        int sin = countSubtrees(a.sin(), cont);
        int des = countSubtrees(a.des(), cont);

        // 1. left subtree is empty & right subtree data matches with root
        // 2. right subtree is empty & left subtree data matches with root
        // 3. both left & right subtree are non-empty & their data matches with
        // root
        if ((sin == Integer.MAX_VALUE && des == a.val()) || (des == Integer.MAX_VALUE && sin == a.val())
                || (sin == a.val() && des == a.val())) {
            cont[0]++;
            return a.val();
        }
        // return infinity if root's data doesn't match with left or right
        // subtree
        return Integer.MAX_VALUE;

    }