Number of Unique Binary Search Trees

Given two integers m and n , n>=m. Find total number of structurally correct BSTs possible with all numbers between m and n (inclusive).

For example, m=3, n=5 then answer is 5.

3                5     3            5          4          
 \              /       \          /         /   \    
  4            4         5        3        3       5        
   \          /         /          \
    5        3         4            4

Let C(n) = Number of ways we can create BST with n as root.

Number of binary search trees = C(root)*C(root.left)*C(root.right);
Now, since there are “n” nodes in BST and let, the number of BST be represented by C(n) for n elements.

We can find the number of BSTs recursively as :
choose 1 as root, no element on the left sub-tree. n-1 elements on the right sub-tree.
Choose 2 as root, 1 element on the left sub-tree. n-2 elements on the right sub-tree.
Choose 3 as root, 2 element on the left sub-tree. n-3 elements on the right sub-tree.

Similarly, for i-th element as the root, i-1 elements on the left and n-i on the right. These sub-trees are also BSTs so we can write :

C(n) = C(0)C(n-1) + C(1)C(n-2) + .....+ C(i-1)C(n-i)..... + C(n-1)C(0)

C(0) = 1, as there is exactly 1 way to make a BST with 0 nodes. 
C(1) = 1, as there is exactly 1 way to make a BST with 1 node.

C(n)=∑C(i−1)C(n−i)

The above summation dissolves into Catalan Number (2nCn)/(n+1).

Recursive Solution
We can do compute the formulae C(n) = C(0)C(n-1) + C(1)C(n-2) + .....+ C(i-1)C(n-i)..... + C(n-1)C(0) by doing recursion where we for each element i in m to n we chose the element i as root and recursively count trees with i-1 element on the left subtree and n-i element on the right subtree.

• Base case: If n is 0 or n is 1, return 1.
• Otherwise, total number of BSTs(n) = total number of BSTs with root as 1 + total number of BSTs with root as 2 + … + total number of BSTs with root as n
• Total number of BSTs with root at index ‘i’ = total number of BSTs(i)*total number of BSTs(n-1-i)

Following is a O(n!) solution.

public static int numOfUniqueBST1(int len){
    if(len <= 1){
      return 1;
    }
    else{
      int count = 0;
      for(int i = 1; i<= len; i++){
       count += numOfUniqueBST1(i-1)*numOfUniqueBST1(len-i);
      }   
      return count;
    }
  }
  
  public static int numOfUniqueBST1(int m, int n) {
    int len = n-m+1;
    return numOfUniqueBST1(len);
  }

Faster Solution – Dynamic Programming

But how we can improve? We can see that there are lot of overlapping subproblems and we are recomputing them all. For example, if n=3,

C(3) = C(0)*C(2)+C(1)*C(1)+C(2)*C(0)

.
So we are computing each of C(0), C(1) and C(2) twice. We can improve by caching the computation in a DP table. Below is an implementation of this approach.

public static int numOfUniqueBSTDP(int n, int[] counts){
	int count = 0;
	if(n < 0){
		return 0;
	}
	if(n <= 1){
		return 1;
	}
	
	//count possible trees with each element as root
	for(int i = 1; i<=n; i++){
		//compute if not in DP
		if(counts[i-1] == -1){
			counts[i-1] = numOfUniqueBSTDP(i-1, counts);
		}
		if(counts[n-i] == -1){
			counts[n-i] = numOfUniqueBSTDP(n-i, counts);
		}
		
		count +=  counts[i-1]*counts[n-i];
	}
	
	return count;
}

public static int numOfUniqueBSTDP(int m, int n){
	int len = n-m+1;
	int[] counts = new int[n+1]; 
	
	//mark each cell not computed
	for(int i = 0; i<=n; i++){
		counts[i] = -1;
	}
	
	return numOfUniqueBSTDP(len, counts);
}