Get the minimum number of comparisons when adding data in a BST

Question

I need to calculate the minimum number of comparisons that the implementation of the BST will be effectuate, given an array of numbers with length N and changing the order in which the elements are added.

For example, if I have an array [1 2 3], it will print that the minimum amount of comparisons with a given order is 2, from the 6 different ways of adding the numbers to the tree.

The code that I actually write may already calculate this, creating a new tree for every combination to find the number of comparisons and finally calculating the minimum value from them by using the method comparisonTree.findMin();. It goes well until the number of elements in the array is bigger; the implementation isn't efficient enough.

The code I use for acquire the combinations is a modified version of the one from Generating all permutations of a given string. I'm searching for a more efficient way for completing this task, if any.

public static int[] readInts(String cad) {
    String lines[] = cad.split("");
    int arr[] = new int[lines.length];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = Integer.parseInt(lines[i]);
    }
    return arr;
}

public static int findMinimumComp(String str, BinarySearchTree<Integer> t) throws Exception {
    BinarySearchTree<Integer> compTree = new BinarySearchTree<>();
    int compAux = 100;
    findMinimumComp("", str, t, compTree, compAux);
    return compTree.findMin();
}

private static BinarySearchTree<Integer> findMinimumComp(String prefix, String str, BinarySearchTree<Integer> t, BinarySearchTree<Integer> compTree, int compAux) throws Exception {
    int n = str.length();
    int arr[] = new int[n];
    int comparation;

    if (n == 0) {
            arr = readInts(prefix);
            for (int a = 0; a < arr.length; a++) { // add elements
                t.insert(arr[a]);
            }
            comparation = t.getCompareCount(); //method for getting number of comparisons

            if (comparation < compAux || compTree.isEmpty()){
                compTree.insert(comparation); //comparisons tree
                compAux = comparation;
            }

            t.initializeCompareCount();
            t.makeEmpty();
    } else {
        for (int i = 0; i < n; i++) {
            findMinimumComp(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), t, compTree, compAux);
        }
    }
    return compTree;
}