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
function calculateFact ( fact , N ) { fact [ 0 ] = 1 ; for ( var i = 1 ; i < N ; i ++ ) { fact [ i ] = fact [ i - 1 ] * i ; } } function nCr ( fact , N , R ) { if ( R > N ) return 0 ; var res = parseInt ( fact [ N ] / fact [ R ] ) ; res = parseInt ( res / fact [ N - R ] ) ; return res ; } function countWays ( arr , fact ) { var N = arr . length ; if ( N <= 2 ) { return 1 ; } var leftSubTree = [ ] ; var rightSubTree = [ ] ; var root = arr [ 0 ] ; for ( var i = 1 ; i < N ; i ++ ) { if ( arr [ i ] < root ) { leftSubTree . push ( arr [ i ] ) ; } else { rightSubTree . push ( arr [ i ] ) ; } } var N1 = leftSubTree . length ; var N2 = rightSubTree . length ; var countLeft = countWays ( leftSubTree , fact ) ; var countRight = countWays ( rightSubTree , fact ) ; return nCr ( fact , N - 1 , N1 ) * countLeft * countRight ; } var arr = [ ] ; arr = [ 3 , 4 , 5 , 1 , 2 ] ; var N = arr . length ; var fact = Array ( N ) ; calculateFact ( fact , N ) ; document . write ( countWays ( arr , fact ) ) ;