human
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"
Solution in Python:
assistant
#Here is code to count permutations of given array that generates the same Binary Search Tree ( BST ) and the other steps required.
 def calculateFact ( fact : list , N : int ) -> None :
	fact [ 0 ] = 1
	for i in range ( 1 , N ) :
		fact [ i ] = fact [ i - 1 ] * i
def nCr ( fact : list , N : int , R : int ) -> int :
	if ( R > N ) :
		return 0
	res = fact [ N ] // fact [ R ]
	res //= fact [ N - R ]
	return res
def countWays ( arr : list , fact : list ) -> int :
	N = len ( arr )
	if ( N <= 2 ) :
		return 1
	leftSubTree = [ ]
	rightSubTree = [ ]
	root = arr [ 0 ]
	for i in range ( 1 , N ) :
		if ( arr [ i ] < root ) :
			leftSubTree . append ( arr [ i ] )
		else :
			rightSubTree . append ( arr [ i ] )
	N1 = len ( leftSubTree )
	N2 = len ( rightSubTree )
	countLeft = countWays ( leftSubTree , fact )
	countRight = countWays ( rightSubTree , fact )
	return ( nCr ( fact , N - 1 , N1 ) * countLeft * countRight )
if __name__ == ' _ _ main _ _ ' :
	arr = [ 3 , 4 , 5 , 1 , 2 ]
	N = len ( arr )
	fact = [ 0 ] * N
	calculateFact ( fact , N )
	print ( countWays ( arr , fact ) )