Count permutations of given array that generates the same Binary Search Tree ( BST ) | Function to precompute the factorial of 1 to N ; Function to get the value of nCr ; nCr = fact ( n ) / ( fact ( r ) * fact ( n - r ) ) ; Function to count the number of ways to rearrange the array to obtain same BST ; Store the size of the array ; Base case ; Store the elements of the left subtree of BST ; Store the elements of the right subtree of BST ; Store the root node ; Push all the elements of the left subtree ; Push all the elements of the right subtree ; Store the size of leftSubTree ; Store the size of rightSubTree ; Recurrence relation ; Driver Code ; Store the size of arr ; Store the factorial up to N ; Precompute the factorial up to N
def calculateFact ( fact : list , N : int ) -> None : NEW_LINE INDENT fact [ 0 ] = 1 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT fact [ i ] = fact [ i - 1 ] * i NEW_LINE DEDENT DEDENT def nCr ( fact : list , N : int , R : int ) -> int : NEW_LINE INDENT if ( R > N ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT res = fact [ N ] // fact [ R ] NEW_LINE res //= fact [ N - R ] NEW_LINE return res NEW_LINE DEDENT def countWays ( arr : list , fact : list ) -> int : NEW_LINE INDENT N = len ( arr ) NEW_LINE if ( N <= 2 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT leftSubTree = [ ] NEW_LINE rightSubTree = [ ] NEW_LINE root = arr [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT if ( arr [ i ] < root ) : NEW_LINE INDENT leftSubTree . append ( arr [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT rightSubTree . append ( arr [ i ] ) NEW_LINE DEDENT DEDENT N1 = len ( leftSubTree ) NEW_LINE N2 = len ( rightSubTree ) NEW_LINE countLeft = countWays ( leftSubTree , fact ) NEW_LINE countRight = countWays ( rightSubTree , fact ) NEW_LINE return ( nCr ( fact , N - 1 , N1 ) * countLeft * countRight ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 4 , 5 , 1 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE fact = [ 0 ] * N NEW_LINE calculateFact ( fact , N ) NEW_LINE print ( countWays ( arr , fact ) ) NEW_LINE DEDENT