Number of ways to construct desired BST

A BST can be constructed from a list of integers with different orders. For example, [4,2,1,3,7,5,8,10] and [4,7,5,8,10,2,3,1] may generate the same BST.

Question: Given a BST, find out the number of integer lists that can generate this BST.

Solution: Based on the following figure, let us do a pre-order traversal, and get a list of possible integers: {4,2,1,3,7,5,8,10}.

It could be noticed that the integers that are smaller than the first entry of the list are the left subTree of the BST. The integers that are greater than the first entry of the list are the right subTree of the BST. Therefore, the input list can be represent as {4, [2,1,3] [7,5,8,10]}.

Furthermore, according to the property of the BST, as long as the relative order of the integers are maintained, the same BST can be generated. For example, in this case {4, [2,[7,5,8,10],1,3]}, or {4, [2,[7,5],1,[8,10],3]}, can generate the same BST.

Therefore, this problem can be converted to the following

Q: How many different ways to maintain the relative orders of the integers in the given list?

To solve this question, we first need to specify tree entries from this list and which will be filled with (2, 1, 3) to form the left subTree. By doing that, the remained 4 entries (excluding the first entry, that is the root) will be filled with (7, 5, 8, 10) to form the right subTree. The questions now becomes: How many different ways can we select such 3 entries (left subTree)? The answer is obvious, it is easy to get that there are 7 choose 3 = 35 ways. Such question can be also represented as How many different ways can we select such 4 entries (right subTree)? The answer is obvious, it is easy to get that there are 7 choose 4 = 35 ways.

Next, the problem becomes how to fill such entry, we can use a recursive way to solve it. For the 3 entries, it should be filled with 2,1 and 3. The root should always be 2, and its left subTree should be (1) and its right subTree should be (3), Therefore, out of is 2 entries (excluding the root entry 2), we need to find out how many ways the left subTree (1) can be placed, the answer should be (2 choose 1) = 2.

For the 4 entries that should be filled with 7,5,8,10. The root is always be 7, and its left subTree should be (5) and its right subTree should be (8,10), therefore, out of its 3 entries, we need to find out how many ways to specify a entry that can be filled with (5) or (8,10). The answer is (3 choose 1) = 3.

I am tired to repeat the process of constructing the tree (8,10). In a similar manner, root is 8, and the answer is (1 choose 1) = (1 choose 0) = 1.

All in all, in this case there are (7 choose 3, root is 4) * (2 choose 1, root is 2) * (3 choose 1, root is 7) * (1 choose 1, root is 8) = 210 ways to construct the desired BST.

Algorithm:

For a given list of integers List.Recursively do the following:
1) If the size of the List is less than 1. return 1.
2) Considering the first entry of the list as the root of the current tree, the rest of the integers in the list should be compared to the root and be treated as the left-subtree, L1, and right-subtree, L2. Be awared that the order of the integers in L1 and L2 should be the same as they are in the list L. After that, Finding out the number of ways to place L1. that is, SizeOf(L)-1 choose SizeOf(L1), and can be denoted as N1.
3) Apply this approach to L1 and L2, the returned values can be denoted as SubN1 and SubN2, return N1 * SubN1 * SubN2.

public static int numberOfWaysToConstructBST(List<int> list)
{
    if (list.Count <= 1)
    return 1;
    else
    {
       List<int> smaller = new List<int>();
       List<int> greater = new List<int>();
       for (int i = 1; i < list.Count; i++)
         if (list[i] < list[0])
            smaller.Add(list[i]);
         else
            greater.Add(list[i]);
       return mChooseN(list.Count - 1, smaller.Count) *
              numberOfWaysToConstructBST(smaller) *
               numberOfWaysToConstructBST(greater);
    }
}

public static int mChooseN(int m, int n)
{
    if (m < 0 || n < 0 || n>) throw new Exception();
    n = m - n > n ? n : m - n;
    int top = 1, bottom = 1;
    while (n > 0)
    {
       top = top * m--;
       bottom = bottom * n--;
    }
     return top / bottom;
}