Number of Binary Search Trees with given right arm stretch

Question

For a given array of distinct (unique) integers I want to know the number of BST in all permutations with right most arm of length k. (If k = 3, root->right->right is a leaf node)

(At my current requirement, I can not afford an algorithm with cost greater than N^3)

Two identical BSTs generated from different permutations are considered different.

My approach so far is:

Assume a function:

F(arr) = {a1, a2, a3...}

where a1 is count of array with k = 1, a2 is count of array with k2 etc.

F(arr[1:n]) = for i in range 1 to n (1 + df * F(subarr where each element is larger than arr[i])) Where df is dynamic factor (n-1)C(count of elements smaller than arr[i])

I am trying to create a dp to solve the problem

• Sort the array
• Start from largest number to smaller number
• dp[i][i] = 1
• for(j in range i-1 to 1) dp[j][i] = some func of dp[j][i-1], but I am unable to formulate

For ex: for arr{4, 3, 2, 1}, I expect the following dp

          arr[i]  4   3   2   1
                +---+---+---+---+
         k = 1  | 1 | 1 | 2 | 6 |
                +---+---+---+---+
         k = 2  | - | 1 | 3 |11 |
                +---+---+---+---+
         k = 3  | - | - | 1 | 6 |
                +---+---+---+---+
         k = 4  | - | - | - | 1 |
                +---+---+---+---+
verification(n!) 1    2   6   24

Any hint, suggestions, pointers or redirection to a good source where I can meet my curiosity is welcome.

Thank you.

edit: It seems I may need 3D dp array. I am working on the same. edit: Corrected col 3 of dp

Answer 1

The good new is that is you don't want the permutation but only their numbers, there is a formula for that. These are know as (unsigned) Stirling numbers of the first kind. The reason for that is that is that the numbers appearing on the right arm of a binary search tree are the left to right minima, that is the i such that the number appearing before i are greater than i. Here is a example where the records are underlined

 6 8 3 5 4 2 7 1 9
 _   _     _   _

This gives the tree

          6
    3           8
 2     5      7   9
1     4  

Those number are know to count permutation according to various characteristics (number of cycles... ). It is know that maxima or minima are among those characteristics. .You can find more information on Entry A008275 of the The On-Line Encyclopedia of Integer Sequences.

Now to answer the question of computing them. Let S(n,k) be the number of permutations of n numbers with k left to right minima. You can use the recurrence:

• S(n, 0) = 0 for all n
• S(n+1, k) = n*S(n, k) + S(n, k-1) for all n>0 and k>0

Answer 2

If I understand your problem correctly.

1. You do not need to sort an array. Since all number in you array are unique, you can assume that every possible subtree is a unique one.

2. Therefore you just need to count how may unique trees you can build having N - k unique elements, where N is a length of your array and k is a length of right most arm. In other words it will be number of permutations of your left subtree if you fix your right subtree to a fixed structure (root (node1 (node2 ... nodeK)))

Here is a way to calculate the number of binary trees of size N:

public int numTrees(int n) {

    int[] ut = new int[Math.max(n + 1, 3)];

    ut[1] = 1;
    ut[2] = 2;

    for (int i = 3; i <= n; i++) {
        int u = 0;
        for (int j = 0; j < i; j++) {
            u += Math.max(1, ut[j]) * Math.max(1, ut[i - j - 1]);
        }
        ut[i] = u;
    }

    return ut[n];
}

it has O(n^2) time complexity and O(n) space complexity.