Total number of possible Binary Search Trees with n keys - GeeksforGeeks
Read full article from Total number of possible Binary Search Trees with n keys - GeeksforGeeks
Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!
package com.ideserve.nilesh.questions;public class NumberOfUniqueBSTs{ // n is input and 'solutions' array stores the intermediate results. All values are initialized to -1 public int computePossibilities(int n, int[] solutions) { if (n < 0) return 0; // error handling : Invalid input else if ((n == 1) || (n == 0)) return 1; // Base cases int possibilities = 0; for (int i = 0; i < n; i++) // for each root { if (solutions[i] == -1) solutions[i] = computePossibilities(i, solutions); // compute all possible BSTs in its left-subtree if (solutions[n-1-i] == -1) solutions[n-1-i] = computePossibilities(n-1-i, solutions); // compute all possible BSTs in its left-subtree possibilities += solutions[i]*solutions[n-1-i]; // multiply these two values and add to total } 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); } |
