Possible number of Trees having N vertex | Java 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
import java . util . * ; class GFG { static int mod = ( int ) ( 1e9 + 7 ) ; static int NumberOfTrees ( int arr [ ] , int N ) { int maxElement = Arrays . stream ( arr ) . max ( ) . getAsInt ( ) ; int level [ ] = new int [ maxElement + 1 ] ; 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 ; } public static void main ( String [ ] args ) { int N = 7 ; int arr [ ] = { 0 , 3 , 2 , 1 , 2 , 2 , 1 } ; System . out . print ( NumberOfTrees ( arr , N ) ) ; } }