Number of ways to reorder array to get same bst

Array Math Divide and Conquer Dynamic Programming Tree Union-Find Binary Search Tree Memoization Combinatorics Binary Tree

54.0% acceptance

Feb 25, 2026

1850

210

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums. Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums. Since the answer may be very large, return it modulo 10^9 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn num_of_ways(nums: Vec<i32>) -> i32 {
    const MOD: u64 = 1_000_000_007;
    // Precompute Pascal's triangle for C(n, k)
    let n = nums.len();
    let mut c = vec![vec![0u64; n + 1]; n + 1];
    for i in 0..=n {
      c[i][0] = 1;
      for j in 1..=i {
        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
      }
    }

    fn dfs(nums: &Vec<i32>, c: &Vec<Vec<u64>>, modv: u64) -> u64 {
      if nums.len() <= 1 {
        return 1;
      }
      let root = nums[0];
      let left: Vec<i32> = nums.iter().filter(|&&x| x < root).cloned().collect();
      let right: Vec<i32> = nums.iter().filter(|&&x| x > root).cloned().collect();
      let l = left.len();
      let r = right.len();
      let ways_left = dfs(&left, c, modv);
      let ways_right = dfs(&right, c, modv);
      // C(l+r, l) * ways_left * ways_right
      c[l + r][l] * ways_left % modv * ways_right % modv
    }

    ((dfs(&nums, &c, MOD) - 1 + MOD) % MOD) as i32
  }
}