Total number of possible Binary Search Trees with n keys?

Solution Approach:

Before going deeper,we should know about Catlan Number.
Here it is:

Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!

For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …. So are numbers of Binary Search Trees.

Implementation:

/**
 *
 */
package com.bst;

/**
 * @author Abhinaw.Tripathi
 *
 */
public class NumberOfBinaryTree
{
   
    public int computePossibilities(int n, int[] solutions)
    {
       
        if (n < 0) return 0;
        else if ((n == 1) || (n == 0)) return 1;
       
        int possibilities = 0;
       
        for (int i = 0; i < n; i++)
        {
            if (solutions[i] == -1)
                solutions[i] = computePossibilities(i, solutions);
               
            if (solutions[n-1-i] == -1)
                solutions[n-1-i] = computePossibilities(n-1-i, solutions);
           
            possibilities += solutions[i]*solutions[n-1-i];
        }
       
        return possibilities;
    }
   
    public int numTrees(int n)
    {
       
        int[] solutions = new int[n];
       
        for (int i = 0; i < n; i++)
            solutions[i] = -1;
       
        return computePossibilities(n, solutions);
    }

   public static void main(String[] args)
   {
       NumberOfBinaryTree solution = new NumberOfBinaryTree();
       
       // print the total number of unique BSTs for n = 3
       System.out.println(solution.numTrees(3));
       
    // print the total number of unique BSTs for n = 4
       System.out.println(solution.numTrees(4));
   }
}