Possible number of Trees having N vertex | javascript program for the above approach ; Function that finds the value of x ^ y using Modular Exponentiation ; Base Case ; If y is odd , multiply x with result ; Return the value ; Function that counts the total number of trees possible ; Find the max element in array ; Level array store the number nodes on level i initially all values are 0 ; In this case tree can not be created ; Calculate level [ i ] ^ level [ i + 1 ] ; Return the final count ; Driver Code ; Given array arr [ ] ; Function call
let mod = 1e9 + 7 ; function power ( x , y ) { if ( y == 0 ) return 1 ; let p = power ( x , y / 2 ) % mod ; p = ( p * p ) % mod ; if ( ( y & 1 ) != 0 ) p = ( x * p ) % mod ; return p ; } function NumberOfTrees ( arr , N ) { let maxElement = Math . max ( ... arr ) ; let level = Array ( maxElement + 1 ) . fill ( 0 ) ; for ( let i = 0 ; i < N ; i ++ ) { level [ arr [ i ] ] ++ ; } if ( arr [ 0 ] != 0 level [ 0 ] != 1 ) { return 0 ; } let ans = 1 ; for ( let i = 0 ; i < maxElement ; i ++ ) { ans = ( ans * power ( level [ i ] , level [ i + 1 ] ) ) % mod ; } return ans ; } let N = 7 ; let arr = [ 0 , 3 , 2 , 1 , 2 , 2 , 1 ] ; document . write ( NumberOfTrees ( arr , N ) ) ;