Introduction

Imagine inserting a sequence of numbers into a Binary Search Tree (BST). The first number becomes the root, smaller values move to the left subtree, and larger values move to the right subtree.

Now consider an interesting question: Can the numbers be rearranged into a different order while producing exactly the same BST?

The answer is yes.

For example, the arrays [2, 1, 3] and [2, 3, 1] produce the same BST. The root remains 2, while 1 belongs to the left subtree and 3 belongs to the right subtree. The insertion order between those two subtrees can change without changing the final tree.

This is the central idea behind LeetCode 1569 – Number of Ways to Reorder Array to Get Same BST.

The challenge is that the number of possible reorderings can grow rapidly. Generating every permutation would be far too expensive. Instead, we can count valid arrangements mathematically using combinations, then combine those counts recursively for the left and right subtrees.

There is one more problem: calculating combinations repeatedly using factorials can lead to unnecessary work and large intermediate numbers. Pascal’s Triangle provides a convenient way to precompute the required combination values.

Let's build the solution from the beginning.

Problem Statement

Problem Link - Number of Ways to Reorder Array to Get Same BST

Given an array nums containing a permutation of the integers from 1 to n, insert its elements in order into an initially empty BST.

Return the number of different reorderings of nums that produce exactly the same BST as the original array.

The original ordering itself is included in the total, but the answer must count only the other reorderings, so the original arrangement must be subtracted once.

Since the answer may be large, return it modulo:

Example 1

The original array creates this BST:

The array [2, 3, 1] creates the same tree.

There are two valid arrangements in total, including the original one. After excluding the original ordering, the answer is 1.

Example 2

There are six valid arrangements in total, including the original sequence. Subtracting the original arrangement gives 5.

Example 3

The BST is a right-skewed tree. Every value must appear in increasing order to produce that same tree, so no alternative ordering exists.

Step 1: The First Element Always Becomes the Root

The first observation comes directly from how a BST is constructed.

Consider:

The first element, 3, becomes the root.

Every remaining value is divided into two groups:

1. Values smaller than 3 go to the left subtree.
2. Values greater than 3 go to the right subtree.

The groups are:

The resulting BST is:

The root must remain 3 in every valid reordering because the first inserted value determines the root.

However, the left and right subtree elements do not necessarily need to appear in one fixed interleaving.

For example, these sequences preserve the same relative order within each subtree:

The left-subtree sequence remains 1, 2, and the right-subtree sequence remains 4, 5.

The elements from the two groups can be mixed together in different ways, provided that the relative insertion order within each group is preserved.

This gives us the first major insight:

Count the valid arrangements of the left subtree, count those of the right subtree, and then count the ways to interleave the two groups.

Step 2: Why Do We Need Combinations (nCr)?

Suppose a node has:

1. L elements in its left subtree.
2. R elements in its right subtree.

After choosing the root, there are L + R remaining positions to fill.

We need to choose which of those positions will contain the left-subtree elements. Once those positions are selected, the remaining positions automatically belong to the right subtree.

The number of ways to choose L positions from L + R positions is:

$[ \binom{L+R}{L} ]$

This is the familiar combinations formula, also written as nCr.

The recursive count becomes:

$[ ways = \binom{L+R}{L} \times waysLeft \times waysRight ]$

Here:

1. waysLeft counts valid reorderings inside the left subtree.
2. waysRight counts valid reorderings inside the right subtree.
3. The combination term counts the possible interleavings of the two groups.

All three factors are necessary.

A small example

Consider the tree formed by:

There is one element on the left and one on the right.

Therefore:

$[ \binom{2}{1}=2 ]$

The two interleavings are:

Both produce the same BST when placed after root 2.

Since each subtree contains only one element, each has exactly one valid arrangement.

Thus:

$[ ways = 2 \times 1 \times 1 = 2 ]$

This count includes the original array. The final answer is:

$[ 2-1=1 ]$

The subtraction is performed only once, after the complete recursive count is calculated.

Step 3: Calculating nCr Efficiently

Now we know how combinations fit into the solution. But how should the values of nCr be calculated?

The mathematical formula is:

$[ \binom{n}{r}=\frac{n!}{r!(n-r)!} ]$

For example:

$[ \binom{4}{2}=\frac{4!}{2!,2!}=6 ]$

One approach is to calculate factorials repeatedly. However, the recursive solution needs combination values at many different subtree sizes. Recalculating factorials again and again adds unnecessary work.

We can instead precompute all the required combinations using Pascal’s Triangle.

The Pascal’s Triangle observation

Every value in Pascal’s Triangle is obtained by adding the two values directly above it:

$[\binom{n-1}{r-1} + \binom{n-1}{r} ]$

The boundary values are always 1:

$[ \binom{n}{0}=\binom{n}{n}=1 ]$

The first few rows look like this:

For example, the value 6 is calculated as:

It represents:

$[ \binom{4}{2}=6 ]$

The same idea can be implemented using a two-dimensional list or array.

Instead of calculating factorials whenever the recursive function needs a combination, we build the table once and look up the required value in constant time.

How the submitted code builds the table

Your solution uses the list liss to store the rows of Pascal’s Triangle.

Each iteration builds one row.

The first and last values of each row are 1. Every interior value is calculated by adding the two entries from the previous row.

For instance, the row representing n = 4 contains:

So when the recursive function needs to choose positions for a left subtree of size 2 from a total of 4 elements, it can retrieve the value 6 directly.

The table is built once before recursion begins.

Step 4: Recursively Count the Left and Right Subtrees

With the combination table ready, the remaining work is recursive.

Your sol() method starts by selecting the first element as the root:

It then separates all remaining elements into two lists:

Because the input contains distinct values, values smaller than the root belong to the left subtree, while larger values belong to the right subtree.

For example:

Next, the function recursively counts the arrangements for both subtrees:

The base case is:

A subtree containing zero or one element has exactly one arrangement. There is nothing to reorder.

Finally, the combination table is used to count the interleavings:

Here:

1. n - 1 is the number of elements remaining after choosing the root.
2. left.size() is the number of positions that must be assigned to the left subtree.
3. z is the number of ways to choose those positions.

The recursive result is then:

In mathematical form:

$[ ways = waysLeft \times waysRight \times \binom{n-1}{leftSize} ]$

The modulo operation keeps the intermediate result within manageable bounds.

Complete Java Solution

The following is the submitted solution, with formatting and explanatory comments added.

Dry Run: How the Pieces Work Together

Consider:

1. Select the root

The first element is 2.

2. Count the subtree arrangements

Both subtrees contain one element.

The base case returns 1 for each subtree.

3. Find the number of interleavings

There are two remaining elements, and one belongs to the left subtree.

The required combination is:

$[ \binom{2}{1}=2 ]$

Pascal’s Triangle gives this value directly.

4. Combine the results

$[ ways = 1 \times 1 \times 2=2 ]$

The two possible arrays are:

Both generate the same BST.

5. Exclude the original ordering

The function initially counts all valid arrangements, including the input array.

Therefore:

The final output is 1, matching the expected result.

Complexity Analysis

Let n be the length of nums.

Building Pascal’s Triangle:

There are (O(n^2)) entries, and each entry is calculated in constant time.

1. Time: (O(n^2))
2. Space: (O(n^2))

Recursive BST counting:

At each recursive call, the elements are divided into left and right lists. Across each level of the recursion, the elements processed total at most (n). In a highly unbalanced BST, the recursion can reach depth (n), and repeatedly scanning and copying the sublists can result in (O(n^2)) total work.

1. Worst-case time: (O(n^2))
2. Additional recursive and sublist space: up to (O(n^2)) across an unbalanced recursion, excluding the combination table.

Therefore, the overall worst-case time complexity of this implementation is:

The Pascal’s Triangle table itself requires:

These bounds are suitable for the problem constraint of n <= 1000.

Important Detail: Why Do We Subtract One?

The recursive function counts all sequences that generate the same BST, including the original input sequence.

However, the problem asks for the number of different reorderings, excluding the original ordering.

That is why the final line is:

This subtraction should happen only once, after the full recursive count has been calculated. Subtracting one inside each recursive call would incorrectly exclude arrangements from individual subtrees.

Interview Takeaway

This problem combines three ideas that are useful in more advanced algorithm questions:

1. Recursive decomposition: The left and right subtrees can be solved independently.
2. Combinatorics: The elements of the two subtrees can be interleaved in (\binom{L+R}{L}) ways.
3. Dynamic programming: Pascal’s Triangle precomputes combination values so they can be reused instead of recalculated.

The most important insight is that the left and right subtree sequences must each preserve their own relative order. Only their positions relative to one another can change.

Once that restriction is understood, the counting formula follows naturally.

Conclusion

LeetCode 1569 looks difficult because it asks for the number of valid reorderings of an array, and the number of possible permutations grows extremely quickly.

The solution becomes manageable when the problem is viewed through the structure of the BST. The first element fixes the root, smaller and larger elements form the left and right subtrees, and the two groups can be interleaved without changing the resulting tree.

Recursion counts the valid arrangements inside each subtree, while combinations count the possible interleavings. Pascal’s Triangle makes those combination values available efficiently, and modular arithmetic keeps the calculations within the required range.

The central formula to remember is:

This is the key to turning a seemingly enormous permutation problem into a structured recursive calculation.