Ways to Reorder Array to Get Same BST
Recursive split with C(n,k)
Recursive decomposition + nCr. Beautiful problem for your background.
Problem
Given an array nums of distinct integers, a BST is built by inserting elements left-to-right (the first element is the root). Return the number of different permutations of nums that would produce the same BST, modulo 10^9 + 7. The answer excludes the original ordering, so subtract 1.
Intuition
The first element is always the root. Elements smaller go left, larger go right. Within each subtree, the relative order must produce the same sub-BST — recursively.
Given left subtree size L and right subtree size R, the number of valid interleavings of two independent sequences is C(L + R, L) — choose which positions in the combined sequence belong to the left subtree.
So: ways(node) = C(L + R, L) * ways(left) * ways(right).
The answer is ways(root) - 1 (exclude the original ordering).
Precompute Pascal's triangle for C(n, k) modular, then recurse.
Same BST Reorder Counting
The root is fixed; reorder left and right subtree values while preserving each subtree shape.
Root partitions values
Every value smaller than root must end up in the left subtree; larger values go right.
Approach
Recursive Split with C(n,k)
O(n²)O(n²)Precompute C[n][k] via Pascal's triangle mod 10^9 + 7. Recurse: for each subtree, partition into left (smaller than root) and right (larger), multiply C(|left|+|right|, |left|) by recursive results.
impl Solution {
pub fn num_of_ways(nums: Vec<i32>) -> i32 {
const MOD: i64 = 1_000_000_007;
let n = nums.len();
// Pascal's triangle.
let mut c = vec![vec![0i64; 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 count(arr: &[i32], c: &[Vec<i64>]) -> i64 {
const MOD: i64 = 1_000_000_007;
if arr.len() <= 1 {
return 1;
}
let root= arr[0];
let left: Vec<i32> = arr[1..].iter().copied().filter(|&x| x < root).collect();
let right: Vec<i32> = arr[1..].iter().copied().filter(|&x| x > root).collect();
let ways = c[left.len() + right.len()][left.len()]
% MOD
* count(&left, c)
% MOD
* count(&right, c)
% MOD;
ways
}
((count(&nums, &c) - 1 + MOD) % MOD) as i32
}
}
function numOfWays(nums: number[]): number {
const MOD = 1_000_000_007n;
const n = nums.length;
const c: bigint[][] = Array.from({ length: n + 1 }, () =>
new Array(n + 1).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;
}
}
const count = (arr: number[]): bigint => {
if (arr.length <= 1) return 1n;
const root = arr[0];
const left = arr.slice(1).filter((x) => x < root);
const right = arr.slice(1).filter((x) => x > root);
return (
((c[left.length + right.length][left.length] *
count(left)) %
MOD *
count(right)) %
MOD
);
};
return Number((count(nums) - 1n + MOD) % MOD);
}Trace
nums = [3, 4, 5, 1, 2]:
Ways to Reorder Array to Get Same BST walkthrough
nums = [3,4,5,1,2]
Root 3 sends [1,2] left and [4,5] right.
Split by the root
Solve both subarrays recursively.
Left ways = 1, right ways = 1.
BST insertion shape is determined by relative comparisons to each root.
Total = 6. Answer = 6 - 1 = 5.
Edge cases
- Sorted input — all elements go right in a chain. Only 1 valid ordering. Answer = 0.
- Reverse sorted — all elements go left. Same: answer = 0.
- Two elements — root + one child.
C(1, 0) = 1orC(1, 1) = 1. Answer = 0. - Balanced split — maximizes the combinatorial factor; gives the largest answer.
Takeaway
BST structure is determined by relative order, not absolute values. The interleaving count C(L + R, L) captures exactly how many ways two independent sequences can be shuffled while preserving their internal orders. This is the same "shuffle" counting that appears in merge-sort analysis and multi-threaded scheduling.