Possible number of Trees having N vertex | Python3 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
mod = int ( 1e9 + 7 ) NEW_LINE def NumberOfTrees ( arr , N ) : NEW_LINE INDENT maxElement = max ( arr ) ; NEW_LINE level = [ 0 ] * ( maxElement + 1 ) ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT level [ arr [ i ] ] += 1 ; NEW_LINE DEDENT if ( arr [ 0 ] != 0 or level [ 0 ] != 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT ans = 1 ; NEW_LINE for i in range ( maxElement ) : NEW_LINE INDENT for j in range ( level [ i + 1 ] ) : NEW_LINE INDENT ans = ( ans * level [ i ] ) % mod ; NEW_LINE DEDENT DEDENT return ans ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 7 ; NEW_LINE arr = [ 0 , 3 , 2 , 1 , 2 , 2 , 1 ] ; NEW_LINE print ( NumberOfTrees ( arr , N ) ) ; NEW_LINE DEDENT