Permutations to Generate Binary Search Tree - Google Top Interview Questions

                        Solution in C++ :

using ll = long long int;
ll mod = 1e9 + 7;
vector<long long> fact;
int N = 1005;
long long power(long long a, long long b) {
    long long result = 1;
    while (b > 0) {
        if (b % 2) result = (result * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return result;
}
long long nCr(int n, int r) {
    ll num = fact[n];
    ll den = (fact[r] * fact[n - r]) % mod;
    ll ans = (num * power(den, mod - 2)) % mod;
    return ans;
}
int dfs(vector<int> curr, int l, int r) {
    int n = curr.size();
    if (n <= 1) return 1;
    ll start = curr[0];
    int p = start - l + 1;
    vector<int> left;
    vector<int> right;
    for (int i = 1; i < curr.size(); i++) {
        if (curr[i] < start)
            left.push_back(curr[i]);
        else
            right.push_back(curr[i]);
    }
    ll ans = nCr(left.size() + right.size(), right.size());
    (ans *= dfs(left, l, start - 1)) %= mod;
    (ans *= dfs(right, start + 1, r)) %= mod;

    return ans;
}
int solve(vector<int>& nums) {
    int n = nums.size();
    fact.resize(N + 1, 1);
    for (int i = 1; i <= N; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    long long ans = dfs(nums, 1, n);
    int res = (ans - 1 + mod) % mod;
    return (int)res;

    return 0;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    private class Node {
        int val;
        int size;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
            this.size = 1;
            this.left = null;
            this.right = null;
        }
    }

    private static final long mod = 1000000007;

    public int solve(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Node root = null;
        for (int num : nums) {
            root = insertIntoBST(root, num);
        }
        int size = nums.length;
        long[][] DP = new long[size + 1][size + 1];
        for (int j = 0; j <= size; j++) {
            DP[0][j] = 1;
        }
        for (int i = 0; i <= size; i++) {
            DP[i][0] = 1;
        }
        for (int j = 1; j <= size; j++) {
            for (int i = 1; i <= size; i++) {
                DP[i][j] = ((DP[i - 1][j] + DP[i][j - 1]) % mod);
            }
        }
        return (((int) getValidPermutationsCount(root, DP)) - 1);
    }

    private long getValidPermutationsCount(Node root, long[][] DP) {
        if (root == null) {
            return 1L;
        }
        int L = 0, R = 0;
        if (root.left != null) {
            L = root.left.size;
        }
        if (root.right != null) {
            R = root.right.size;
        }
        long TL = getValidPermutationsCount(root.left, DP);
        long TR = getValidPermutationsCount(root.right, DP);
        return ((((TL * DP[L][R]) % mod) * TR) % mod);
    }

    private Node insertIntoBST(Node root, int val) {
        if (root == null) {
            return new Node(val);
        }
        root.size++;
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums):
        Mod = 1000000007

        n = len(nums)
        p = [1] * (n + 1)
        for i in range(n):
            p[i + 1] = p[i] * (i + 1)

        def combi(x, y):
            return p[x] * pow(p[y] * p[x - y] % Mod, Mod - 2, Mod) % Mod

        def go(r):
            if len(r) < 2:
                return 1
            x = r[0]
            a, b = [], []
            for i in range(1, len(r)):
                if r[i] < x:
                    a += (r[i],)
                else:
                    b += (r[i],)
            return go(a) * go(b) % Mod * combi(len(r) - 1, len(a)) % Mod

        return (go(nums) - 1 + Mod) % Mod