Saved Bookmarks
| 1. |
Write a function to find number of structurally unique binary trees are possible |
|
Answer» Input: N = 3 Output: 5 for N = 3, there are 5 possible BSTs: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 class Solution{ public: //function to calculate binomial coefficient C(n,k) long long int binomialCoefficient(long long int n, long long int k) { long long int res = 1; if (k > n - k) k = n - k; for (long long int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } //function to calculate Nth Catalan Number long long int catalanNumber(long long in n) { // Calculate value of 2nCn long long int C = binomialCoefficient(2*n, n); // return 2nCn/(n+1) return C/(n+1); } //Function to return the total number of possible unique BST. long long int numOfUniqueBinarySearchTrees(int n) { // find nth catalan number long long int countOfUniqueBinarySearchTrees = catalanNumber(n); // return nth catalan number return countOfUniqueBinarySearchTrees; } };
|
|