Number of Ways to Reorder Array to Get Same BST | C++ | Recursive
The problem could be solved using recusion as the problem could be broken down into smaller overlapping subproblems.\n\nThe first node would always be the root 
The problem could be solved using recusion as the problem could be broken down into smaller overlapping subproblems.\n\nThe first node would always be the root node so it can\'t be rearranged to any other place. For the rest of the nodes the nodes smaller than the root node would have the same ordering and the nodes larger than the root node would also have the same ordering in the final array but the nodes could be rearranged between the larger nodes and smaller nodes.\n\n\n\nThe problem then simply becomes to find in how many ways can we c(elements smaller than root) numbers in n-1(total available places after removing the roor) places which could be calculated using nCr.\n```\nFor [3,4,5,1,2], in all arrays 3 would always stay at nums[0] as it has to be the root node\nNow, in all arrays [1,2] and [4,5] needs to be in same order as changing the order would result in change in the corresponding subtree.\n\nBut the two arrays [1,2] and [4,5] could be arranged among themselves.\nThat would simply mean we have to find 2 places for [1,2] out of the 4 availble places which means the answer would be 4C2.\n\nThen we need to recusively find the answer for [1,2] and [4,5]\n\n```\n\nC++\n\n```\nclass Solution {\npublic:\n    const long long mod = 1e9+7;\n    vector<long long> fact;\n    void calcFact()\n    {\n        fact[0]=1;\n        fact[1]=1;\n        for(long long i=2;i<1001;i++)\n            fact[i]=(fact[i-1]*i)%mod;\n    }\n    \n    long long modInv(long long n,long long p)\n    {\n        if(p==0)\n            return 1LL;\n        long long ans=modInv(n,p/2);\n        if(p&1)\n            return (((ans*ans)%mod)*n)%mod;\n        else\n            return (ans*ans)%mod;\n    }\n    \n    long long helper(vector<int> &nums)\n    {\n        if(nums.size()<=2)  // if the length of array is less than equal to 2 there is only 1 way to arrange it\n            return 1LL;\n        vector<int> small,large;  // store elements smaller and larger than the root node\n        for(int i=1;i<nums.size();i++)\n        {\n            if(nums[i]>nums[0])\n                large.push_back(nums[i]);\n            else small.push_back(nums[i]);\n        }\n        long long ans=1;\n        ans=(ans*fact[(int)nums.size()-1])%mod;\n        ans=(ans*modInv(fact[(int)nums.size()-(int)small.size()-1],mod-2))%mod;  // if m is prime, modular inverse is simply pow(n,m-2)\n        ans=(ans*modInv(fact[(int)small.size()],mod-2))%mod;  // find nCr\n        ans=(ans*helper(small))%mod;  //recursively solve for smaller array \n        ans=(ans*helper(large))%mod;  //recursively solve for smaller array\n        return ans;\n    }\n    \n    \n    int numOfWays(vector<int>& nums) {\n        fact=vector<long long> (1001);\n        calcFact(); // maintain a factorial array to find nCr\n        long long ans= helper(nums);\n        ans--;  // subtract 1 for the original array\n        ans=(ans+mod)%mod;\n        return ans;\n    }\n};\n```
[]