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.
nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.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 109 + 7.
Example 1:
Input: nums = [2,1,3] Output: 1 Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.
Example 2:
Input: nums = [3,4,5,1,2] Output: 5 Explanation: The following 5 arrays will yield the same BST: [3,1,2,4,5] [3,1,4,2,5] [3,1,4,5,2] [3,4,1,2,5] [3,4,1,5,2]
Example 3:
Input: nums = [1,2,3] Output: 0 Explanation: There are no other orderings of nums that will yield the same BST.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= nums.lengthnums are distinct.Problem Overview: Given an array of distinct integers, insert the values into a Binary Search Tree in the given order. The task is to count how many different reorderings of the array generate the exact same BST structure. The answer can be large, so results are computed modulo 1e9 + 7.
Approach 1: Divide and Conquer with Combinatorial Counting (O(n^2) time, O(n^2) space)
The first element of the array always becomes the BST root. All smaller values must appear in the left subtree and larger values in the right subtree. Split the remaining elements into two arrays using this rule. Recursively compute the number of valid reorderings for the left and right subtrees. The key insight: while elements must preserve their internal order relative to each subtree, they can interleave in many ways. Use combinations C(leftSize + rightSize, leftSize) to count how many ways the two sequences can merge. Multiply this by the recursive counts from both sides. Precompute combinations using Pascal's triangle or factorials with modular inverse. This technique relies heavily on divide and conquer and combinatorics.
Approach 2: Dynamic Programming with Memoized Combinations (O(n^2) time, O(n^2) space)
This approach uses the same BST partitioning idea but focuses on efficient combination calculation. Instead of recomputing binomial coefficients repeatedly, build a DP table where dp[i][j] stores C(i, j). Fill the table using Pascal's identity: C(n, k) = C(n-1, k-1) + C(n-1, k). During recursion, split the array into left and right partitions based on the root value, recursively compute subtree counts, and combine them with dp[leftSize + rightSize][leftSize]. Memoization prevents recomputation of subtree results. The recursion essentially simulates BST construction while DP handles combinatorial counting. This approach integrates dynamic programming with binary search tree properties.
Recommended for interviews: The divide-and-conquer combinatorial approach is what interviewers expect. It demonstrates understanding of BST insertion rules and combinatorial interleavings. Starting with the recursive partitioning idea shows strong reasoning. Adding precomputed combinations or DP optimization proves you can scale the solution to large inputs efficiently.
This approach uses divide and conquer combined with combinatorial mathematics to determine the number of ways to reorder an array to produce the same BST. The core idea is to recursively split the array into left and right subarrays (as in constructing the BST) and calculate the number of reorderings for each subtree, using combinations to determine how to arrange elements between left and right subarrays.
The solution defines a recursive function count(), which calculates the number of ways to split and merge according to the current root node by checking elements less than (left subtree) and greater than (right subtree) the root. The function comb() is used to calculate the number of ways to interleave left and right subtrees, and this is done recursively. The result is reduced by 1 since the original order is not counted as a valid reordering.
Time Complexity: O(n^2), where n is the size of the array, due to the recursive division and combination calculation.
Space Complexity: O(n^2), because of temporary lists created for left and right subarrays.
Leverage dynamic programming to memoize previously computed results for subarrays. This reduces redundant calculations by storing results of similar subproblems, enabling more efficient computation of the number of reorderings that yield an equivalent BST structure.
The C++ code uses a memoization approach to store combination calculations in a comb table. The dfs function divides the array, computes the number of left and right subarray reorderings, and memoizes the combinations calculated. This avoids redundant calculations and optimizes efficiency.
Time Complexity: O(n^2), due to dynamic programming table filling and repeated subproblem computations.
Space Complexity: O(n^2), necessary for memoization of the combination results and recursive call stack.
We design a function dfs(nums), which is used to calculate the number of solutions of the binary search tree with nums as nodes. Then the answer is dfs(nums)-1, because dfs(nums) calculates the number of solutions of the binary search tree with nums as nodes, while the problem requires the number of solutions of the binary search tree with nums as nodes after reordering, so the answer needs to be subtracted by one.
Next, let's take a look at how dfs(nums) is calculated.
For an array nums, its first element is the root node, so its left subtree elements are smaller than it, and its right subtree elements are larger than it. So we can divide the array into three parts, the first part is the root node, the second part is the elements of the left subtree, denoted as left, and the third part is the elements of the right subtree, denoted as right. Then, the number of elements in the left subtree is m, and the number of elements in the right subtree is n, so the number of solutions for left and right are dfs(left) and dfs(right) respectively. We can choose m positions from m + n positions in array nums to place the elements of the left subtree, and the remaining n positions to place the elements of the right subtree, so that we can ensure that the reordered binary search tree is the same as the original array nums. Therefore, the calculation method of dfs(nums) is:
$
dfs(nums) = C_{m+n}^m times dfs(left) times dfs(right)
where C_{m+n}^m represents the number of schemes to select m positions from m + n positions, which we can get through preprocessing.
Note the modulo operation of the answer, because the value of dfs(nums) may be very large, so we need to take the modulo of each step in the calculation process, and finally take the modulo of the entire result.
The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of array nums$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Divide and Conquer with Combinatorial Counting | Time Complexity: O(n^2), where n is the size of the array, due to the recursive division and combination calculation. |
| Dynamic Programming | Time Complexity: O(n^2), due to dynamic programming table filling and repeated subproblem computations. |
| Combination Counting + Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer with Combinatorial Counting | O(n^2) | O(n^2) | General case; preferred interview solution using recursion and combinatorics |
| Dynamic Programming with Memoized Combinations | O(n^2) | O(n^2) | When repeatedly computing combinations; avoids recalculating binomial coefficients |
LeetCode 1569. Number of Ways to Reorder Array to Get Same BST • Happy Coding • 8,242 views views
Watch 9 more video solutions →Practice Number of Ways to Reorder Array to Get Same BST with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor