Count permutations of given array that generates the same Binary Search Tree ( BST ) | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void calculateFact ( int fact [ ] , int N ) { fact [ 0 ] = 1 ; for ( long long int i = 1 ; i < N ; i ++ ) { fact [ i ] = fact [ i - 1 ] * i ; } } 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 ; } int countWays ( vector < int > & arr , int fact [ ] ) { int N = arr . size ( ) ; if ( N <= 2 ) { return 1 ; } vector < int > leftSubTree ; vector < int > rightSubTree ; int root = arr [ 0 ] ; for ( int i = 1 ; i < N ; i ++ ) { if ( arr [ i ] < root ) { leftSubTree . push_back ( arr [ i ] ) ; } else { rightSubTree . push_back ( arr [ 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 ; } int main ( ) { vector < int > arr ; arr = { 3 , 4 , 5 , 1 , 2 } ; int N = arr . size ( ) ; int fact [ N ] ; calculateFact ( fact , N ) ; cout << countWays ( arr , fact ) ; return 0 ; }