Possible number of Trees having N vertex | C ++ program for the above approach ; Function to count the total number of trees possible ; Find the max element in the given array ; Level array store the number of nodes on level i initially all values are zero ; In this case tree can not be created ; To store the count of trees ; Iterate until maxElement ; Calculate level [ i ] ^ level [ i + 1 ] ; Update the count of tree ; Return the final count of trees ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int mod = 1e9 + 7 ; int NumberOfTrees ( int arr [ ] , int N ) { int maxElement = * max_element ( arr , arr + N ) ; int level [ maxElement + 1 ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { level [ arr [ i ] ] ++ ; } if ( arr [ 0 ] != 0 level [ 0 ] != 1 ) { return 0 ; } int ans = 1 ; for ( int i = 0 ; i < maxElement ; i ++ ) { for ( int j = 0 ; j < level [ i + 1 ] ; j ++ ) { ans = ( ans * level [ i ] ) % mod ; } } return ans ; } int main ( ) { int N = 7 ; int arr [ ] = { 0 , 3 , 2 , 1 , 2 , 2 , 1 } ; cout << NumberOfTrees ( arr , N ) ; return 0 ; }