Count permutations of given array that generates the same Binary Search Tree ( BST ) | Java program to implement the above approach ; 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
import java . util . * ; class GFG { static void calculateFact ( int fact [ ] , int N ) { fact [ 0 ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) { fact [ i ] = fact [ i - 1 ] * i ; } } static int nCr ( int fact [ ] , int N , int R ) { if ( R > N ) return 0 ; int res = fact [ N ] / fact [ R ] ; res /= fact [ N - R ] ; return res ; } static int countWays ( Vector < Integer > arr , int fact [ ] ) { int N = arr . size ( ) ; if ( N <= 2 ) { return 1 ; } Vector < Integer > leftSubTree = new Vector < Integer > ( ) ; Vector < Integer > rightSubTree = new Vector < Integer > ( ) ; int root = arr . get ( 0 ) ; for ( int i = 1 ; i < N ; i ++ ) { if ( arr . get ( i ) < root ) { leftSubTree . add ( arr . get ( i ) ) ; } else { rightSubTree . add ( arr . get ( i ) ) ; } } int N1 = leftSubTree . size ( ) ; int N2 = rightSubTree . size ( ) ; int countLeft = countWays ( leftSubTree , fact ) ; int countRight = countWays ( rightSubTree , fact ) ; return nCr ( fact , N - 1 , N1 ) * countLeft * countRight ; } public static void main ( String [ ] args ) { int [ ] a = { 3 , 4 , 5 , 1 , 2 } ; Vector < Integer > arr = new Vector < Integer > ( ) ; for ( int i : a ) arr . add ( i ) ; int N = a . length ; int [ ] fact = new int [ N ] ; calculateFact ( fact , N ) ; System . out . print ( countWays ( arr , fact ) ) ; } }