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)); } }

#DataStructure #Algorithms #CoreJava