Number of Ways to Reorder Array to Get Same BST — Solution
Number of Ways to Reorder Array to Get Same BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Ways to Reorder Array to Get Same BST is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Math, Divide and Conquer, Combinatorics
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums is a permutation of distinct integers. Inserting them left to right into an empty binary search tree produces some tree.
Return the number of other orderings of nums that produce the identical tree, modulo 10⁹ + 7.
Example 1
Input: nums = [2,1,3]
Output: 1
Explanation: `[2,3,1]` builds the same tree.
Example 2
Input: nums = [3,4,5,1,2]
Output: 5
Example 3
Input: nums = [1,2,3]
Output: 0
Explanation: The tree is a right chain, so the order is forced.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= nums.lengthAll integers in nums are distinct.
Hints for Number of Ways to Reorder Array to Get Same BST
Hint 1
The first element must stay first — it is the root.
Hint 2
The elements smaller than the root form the left subtree, the rest the right, and their relative orders are each fixed independently.
Hint 3
So the count is
C(n-1, leftSize)times the counts for the two subtrees.
How to solve Number of Ways to Reorder Array to Get Same BST
Recursive counting. The root is forced to come first. The remaining n - 1 elements split into the left and right subtrees, and any interleaving of the two sequences produces the same tree — C(n-1, |left|) of them — while the internal order of each side is counted recursively. Subtract 1 at the end to exclude the original ordering.
Approach
- Build Pascal's triangle up to
nfor the binomials. - Recursively: a sequence of length at most 2 has exactly one arrangement.
- Otherwise split on the first element, and return
C(len-1, |left|) · count(left) · count(right). - Return
count(nums) - 1modulo 10⁹ + 7.
Why it works
Interleaving is free because insertion into a BST routes each value by comparison with the root — a left-subtree value and a right-subtree value never interact, so their relative order between the two groups is irrelevant. Building the binomials with Pascal's triangle sidesteps modular inverses entirely, which at n <= 1000 costs a megabyte of additions and nothing else.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- The answer excludes the original ordering, hence the
- 1. - That subtraction can go negative under the modulus — add the modulus back.
- Multiplying two residues near 10⁹ needs 64-bit arithmetic, or a split multiply in JavaScript.
Reference solution
Python
from math import comb
from typing import List
def numOfWays(nums: List[int]) -> int:
MOD = 10**9 + 7
def count(seq: List[int]) -> int:
if len(seq) <= 2:
return 1
root = seq[0]
left = [v for v in seq[1:] if v < root]
right = [v for v in seq[1:] if v > root]
return comb(len(seq) - 1, len(left)) * count(left) % MOD * count(right) % MOD
return (count(nums) - 1) % MODJava
public static int numOfWays(int[] nums) {
final long MOD = 1000000007L;
int n = nums.length;
long[][] binom = new long[n + 1][];
for (int i = 0; i <= n; i++) {
binom[i] = new long[i + 1];
Arrays.fill(binom[i], 1);
for (int j = 1; j < i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
}
List<Integer> seq = new ArrayList<>();
for (int v : nums) seq.add(v);
long total = nowCount(seq, binom, MOD);
return (int) ((total - 1 + MOD) % MOD);
}
private static long nowCount(List<Integer> seq, long[][] binom, long MOD) {
if (seq.size() <= 2) return 1;
int root = seq.get(0);
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
for (int i = 1; i < seq.size(); i++) {
if (seq.get(i) < root) left.add(seq.get(i));
else right.add(seq.get(i));
}
long ways = binom[seq.size() - 1][left.size()];
ways = ways * nowCount(left, binom, MOD) % MOD;
ways = ways * nowCount(right, binom, MOD) % MOD;
return ways;
}C++
static long long nowCount(vector<int>& seq, vector<vector<long long>>& binom, long long MOD) {
if (seq.size() <= 2) return 1;
int root = seq[0];
vector<int> left, right;
for (size_t i = 1; i < seq.size(); i++) {
if (seq[i] < root) left.push_back(seq[i]);
else right.push_back(seq[i]);
}
long long ways = binom[seq.size() - 1][left.size()];
ways = ways * nowCount(left, binom, MOD) % MOD;
ways = ways * nowCount(right, binom, MOD) % MOD;
return ways;
}
int numOfWays(vector<int>& nums) {
const long long MOD = 1000000007LL;
int n = (int) nums.size();
vector<vector<long long>> binom(n + 1);
for (int i = 0; i <= n; i++) {
binom[i].assign(i + 1, 1);
for (int j = 1; j < i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
}
vector<int> seq = nums;
long long total = nowCount(seq, binom, MOD);
return (int) ((total - 1 + MOD) % MOD);
}JavaScript
var numOfWays = function(nums) {
var MOD = 1000000007;
var n = nums.length, i, j;
var mulmod = function(a, b) {
var hi = Math.floor(a / 65536), lo = a % 65536;
return ((hi * b % MOD) * 65536 + lo * b) % MOD;
};
var binom = [];
for (i = 0; i <= n; i++) {
var row = [];
for (j = 0; j <= i; j++) row.push(1);
for (j = 1; j < i; j++) row[j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
binom.push(row);
}
var count = function(seq) {
if (seq.length <= 2) return 1;
var root = seq[0];
var left = [], right = [];
for (var t = 1; t < seq.length; t++) {
if (seq[t] < root) left.push(seq[t]); else right.push(seq[t]);
}
var ways = binom[seq.length - 1][left.length];
ways = mulmod(ways, count(left));
ways = mulmod(ways, count(right));
return ways;
};
return (count(nums) - 1 + MOD) % MOD;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming