Number of Ways to Reorder Array to Get Same BST

hard dp tree combinatorics

Problem

You are given an array nums that is a permutation of the integers 1..n. Inserting the values into an initially empty binary search tree (BST) in the given left-to-right order produces some tree. Count how many different orderings of the same values build the exact same BST shape, not counting the original ordering itself. Return the count modulo 10^9 + 7.

Inputnums = [3, 4, 5, 1, 2]

Output5

The root is 3. Values smaller than 3 form the left group [1, 2]; larger ones form the right group [4, 5]. Each group must keep its own relative order, but the two groups can be interleaved freely after the root. There are 6 total orderings that yield this tree; excluding the original gives 5.

nums (permutation, comma-separated)

def num_of_ways(nums):
    MOD = 10**9 + 7
    n = len(nums)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        C[i][0] = 1
        for j in range(1, i + 1):
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD

    def count(group):
        if len(group) <= 2:
            return 1
        root = group[0]
        left = [x for x in group if x < root]
        right = [x for x in group if x > root]
        ways = C[len(group) - 1][len(left)]
        ways = ways * count(left) % MOD
        ways = ways * count(right) % MOD
        return ways % MOD

    return (count(nums) - 1) % MOD

function numOfWays(nums) {
  const MOD = 1000000007n, n = nums.length;
  const C = Array.from({ length: n }, () => new Array(n).fill(0n));
  for (let i = 0; i < n; i++) {
    C[i][0] = 1n;
    for (let j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
  }
  function count(group) {
    if (group.length <= 2) return 1n;
    const root = group[0];
    const left = group.filter((x) => x < root);
    const right = group.filter((x) => x > root);
    let ways = C[group.length - 1][left.length];
    ways = ways * count(left) % MOD;
    ways = ways * count(right) % MOD;
    return ways % MOD;
  }
  return Number((count(nums) - 1n + MOD) % MOD);
}

class Solution {
    long MOD = 1000000007L;
    long[][] C;
    public int numOfWays(int[] nums) {
        int n = nums.length;
        C = new long[n][n];
        for (int i = 0; i < n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++)
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
        List<Integer> all = new ArrayList<>();
        for (int x : nums) all.add(x);
        return (int) ((count(all) - 1 + MOD) % MOD);
    }
    long count(List<Integer> group) {
        if (group.size() <= 2) return 1;
        int root = group.get(0);
        List<Integer> left = new ArrayList<>(), right = new ArrayList<>();
        for (int x : group) {
            if (x < root) left.add(x);
            else if (x > root) right.add(x);
        }
        long ways = C[group.size() - 1][left.size()];
        ways = ways * count(left) % MOD;
        ways = ways * count(right) % MOD;
        return ways % MOD;
    }
}

long long MOD = 1000000007LL;
vector<vector<long long>> C;
long long count(vector<int>& group) {
    if ((int)group.size() <= 2) return 1;
    int root = group[0];
    vector<int> left, right;
    for (int x : group) {
        if (x < root) left.push_back(x);
        else if (x > root) right.push_back(x);
    }
    long long ways = C[group.size() - 1][left.size()];
    ways = ways * count(left) % MOD;
    ways = ways * count(right) % MOD;
    return ways % MOD;
}
int numOfWays(vector<int>& nums) {
    int n = nums.size();
    C.assign(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
    return (int)((count(nums) - 1 + MOD) % MOD);
}

Explanation

When you insert values into a BST one by one, the first value always becomes the root. Every later value smaller than the root ends up somewhere in the left subtree, and every value larger ends up on the right. So the tree shape is decided entirely by which values are smaller or larger than each root, never by exactly when they arrive.

That means two orderings build the same tree as long as, within the left group and within the right group, the relative order of the values is unchanged. The left group is itself a sequence whose first element is the root of the left subtree, and likewise for the right. So the problem is recursive.

Now think about interleaving. After we fix the root, we have L values destined for the left and R for the right, a total of L + R slots. We may place them in any order as long as the left values keep their internal order and the right values keep theirs. The number of ways to choose which of the L + R slots go to the left group is the binomial coefficient C(L + R, L).

Multiplying across the recursion gives ways(group) = C(L + R, L) · ways(left) · ways(right). A group of size 0, 1, or 2 has exactly one arrangement, so it contributes a factor of 1 and stops the recursion.

For nums = [3, 4, 5, 1, 2]: root 3 splits into left [1, 2] and right [4, 5], so C(4, 2) = 6, and each side has just one arrangement. The total number of equivalent orderings is 6. We subtract 1 to drop the original ordering, leaving 5. We precompute the binomial coefficients with Pascal's triangle and keep everything modulo 10^9 + 7.

Time: O(n²) Space: O(n²)