Prerequisite: Total number of possible Binary Search Trees with n keys
Given an array arr[] of N integers. The task is to count the number of Binary Search Tree can be made using each node of element in arr[] as a root node.
Examples:
Input: arr[] = { 20, 10, 30 }
Output: 1 2 2
Input: arr[] = { 1, 2, 3, 4, 5 }
Output: 14 5 4 5 14
Approach:
The total number of possible Binary Search Tree(BST) is given by Catalan Number:
Cn = (2n)!/(( n+1)!*n!) where n = number of distinct keys.
- Count the number of element(say c1) less than the current node.
- Count the number of element(say c2) greater than the current node.
- Then total number of Binary Search Tree(BST) can be formed using current element as a root node is equals to the product of total number of BST formed using c1 elements and total number of BST formed using c2 elements.
Total Number of BST = Cc1*Cc2
Below is the implementation of the above approach:
C++
// C++ implementation of the above code #include <iostream>using namespace std;// A function to find factorial of a // given number int fact(int num) { int fact = 1; while(num > 1) { fact *= num; num -= 1; } return fact; } // Find nth catalan number int catalan(int n) { return fact(2 * n)/(fact(n) * fact(n + 1)) ; } // Driver Code int main() { // size of arr[] int n = 5; // Elements in arr[] int arr[] = {1, 2, 3, 4, 5}; int i,k; for(k = 0; k < n; k++) { int s = 0; // Count the number of element // less than current element // in arr[k] for(i = 0; i < n; i++) { if (arr[i] < arr[k]) s += 1 ; } // Here s = number of node in left // BST and (n-s-1) = number of node // in right BST // Find number of BST using elements // in left BST int catalan_leftBST = catalan(s) ; // Find number of BST using elements // in right BST int catalan_rightBST = catalan(n - s - 1) ; // Find total number of BST int totalBST = catalan_rightBST * catalan_leftBST ; // Print total BST count cout<< totalBST << " " ; } } // This code is contributed by AnkitRai01 |
Java
// java implementation of the above codepublic class GFG { // A function to find factorial of a // given number static int fact(int num){ int fact = 1; while(num > 1) { fact *= num; num -= 1; } return fact; }// Find nth catalan number static int catalan(int n){ return fact(2 * n)/(fact(n) * fact(n + 1)) ;}// Driver Code public static void main (String[] args) { // size of arr[] int n = 5; // Elements in arr[] int arr[] = {1, 2, 3, 4, 5}; int i,k; for(k = 0; k < n; k++) { int s = 0; // Count the number of element // less than current element // in arr[k] for(i = 0; i < n; i++) { if (arr[i] < arr[k]) s += 1 ; } // Here s = number of node in left // BST and (n-s-1) = number of node // in right BST // Find number of BST using elements // in left BST int catalan_leftBST = catalan(s) ; // Find number of BST using elements // in right BST int catalan_rightBST = catalan(n - s - 1) ; // Find total number of BST int totalBST = catalan_rightBST * catalan_leftBST ; // Print total BST count System.out.print(totalBST + " ") ; }}}// This code is contributed by AnkitRai01 |
Python3
# A function to find factorial of a # given number def fact(num): fact = 1; while(num>1): fact = fact * num; num = num-1; return fact; # Find nth catalan numberdef catalan(n): return fact(2 * n)//(fact(n)*fact(n + 1))# Driver Code if __name__ == '__main__': # size of arr[] n = 5 # Elements in arr[] arr = [1, 2, 3, 4, 5] for k in range(n): s = 0 # Count the number of element # less than current element # in arr[k] for i in range(n): if arr[i] < arr[k]: s+= 1 # Here s = number of node in left # BST and (n-s-1) = number of node # in right BST # Find number of BST using elements # in left BST catalan_leftBST = catalan(s) # Find number of BST using elements # in right BST catalan_rightBST = catalan(n-s-1) # Find total number of BST totalBST = catalan_rightBST * catalan_leftBST # Print total BST count print(totalBST, end =" ") |
C#
// C# implementation of the above codeusing System;class GFG { // A function to find factorial of a // given number static int fact(int num){ int fact = 1; while(num > 1) { fact *= num; num -= 1; } return fact; } // Find nth catalan number static int catalan(int n){ return fact(2 * n)/(fact(n) * fact(n + 1)) ;} // Driver Code public static void Main(String[] args) { // size of []arr int n = 5; // Elements in []arr int []arr = {1, 2, 3, 4, 5}; int i,k; for(k = 0; k < n; k++) { int s = 0; // Count the number of element // less than current element // in arr[k] for(i = 0; i < n; i++) { if (arr[i] < arr[k]) s += 1 ; } // Here s = number of node in left // BST and (n-s-1) = number of node // in right BST // Find number of BST using elements // in left BST int catalan_leftBST = catalan(s) ; // Find number of BST using elements // in right BST int catalan_rightBST = catalan(n - s - 1) ; // Find total number of BST int totalBST = catalan_rightBST * catalan_leftBST ; // Print total BST count Console.Write(totalBST + " ") ; }}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the above code // A function to find factorial of a // given number function fact(num) { var fact = 1; while(num > 1) { fact *= num; num -= 1; } return fact; } // Find nth catalan number function catalan(n) { return fact(2 * n)/(fact(n) * fact(n + 1)) ; } // Driver Code // size of arr[] var n = 5; // Elements in arr[] var arr = [1, 2, 3, 4, 5] ; var i,k; for(k = 0; k < n; k++) { var s = 0; // Count the number of element // less than current element // in arr[k] for(i = 0; i < n; i++) { if (arr[i] < arr[k]) s += 1 ; } // Here s = number of node in left // BST and (n-s-1) = number of node // in right BST // Find number of BST using elements // in left BST var catalan_leftBST = catalan(s) ; // Find number of BST using elements // in right BST var catalan_rightBST = catalan(n - s - 1) ; // Find total number of BST var totalBST = catalan_rightBST * catalan_leftBST ; // Print total BST count document.write( totalBST + " "); } </script> |
Output:
14 5 4 5 14
Time Complexity: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
