C++ || WITH FULL EXPLANATION || EASY
We know that in bst all the nodes to the left are less than the root node and all the nodes to the right are greater than the root node. So in order to create s
We know that in bst all the nodes to the left are less than the root node and all the nodes to the right are greater than the root node. So in order to create same bst we will have to use same root as first node and consider relative ordering independently of left and right sub part.\n\nIt took me while to understand the concept so this is the explanation!\nlets consider example\n[3,4,5,1,2]\nhere root=3;\nleft=[1,2];\nright=[4,5];\nnow to get same bst 1 should always appear before 2.\nin right part 4 should appear before 5.\nbut there is no restriction on order of left and right ordering.Like 4 and 2 can occur in any order.\nNow to get total results first of all the the length of left=l;\nlength of right= r;\ntotal length= l+r;\nwe have l+r position out of which l position has to be selected for the left elements and they will appear in same order.\nso no of ways= length(c)left\nnow for left and right subtree we call the recursive function and multiply the total result.\n\n```\nclass Solution {\npublic:\n    int mod=1e9+7;\n        int countBST(vector<int>& nums) {\n        if (nums.size() <= 2)\n            return 1;\n\n        vector<int> left, right;\n        int root = nums[0];\n\n        for (int i = 1; i < nums.size(); i++) {\n            if (nums[i] < root)\n                left.push_back(nums[i]);\n            else\n                right.push_back(nums[i]);\n        }\n\n        long long l = countBST(left);  \n        long long r = countBST(right);\n\n        // Calculate the number of combinations using the Catalan number formula\n        long long tc = binomialCoefficient(left.size() + right.size(), left.size());\n\n        return (l * r % 1000000007 * tc % 1000000007);\n    }\n    \n\n    long long binomialCoefficient(int n, int k) {\n        const int MOD = 1e9 + 7;\n\n        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));\n        dp[0][0] = 1;\n\n        for (int i = 1; i <= n; i++) {\n            dp[i][0] = 1;\n            for (int j = 1; j <= min(i, k); j++) {\n                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;\n            }\n        }\n\n        return dp[n][k];\n    }\n    int numOfWays(vector<int>& nums) {\n        const int MOD = 1e9 + 7;\n        return (countBST(nums) - 1 + MOD) % MOD;\n        \n    }\n};\n\n\n
['Binary Search Tree', 'C', 'Combinatorics']