LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST

LeetCode Problem 1569

Difficulty: 🔴 Hard
Topics: Array, Math, Divide and Conquer, Dynamic Programming, Tree, Union-Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree

Solution

Problem Understanding

The problem gives us a permutation of integers from 1 to n, and we insert the numbers into an initially empty Binary Search Tree (BST) in the exact order they appear in the array.

A BST has the following property:

• Values smaller than the current node go to the left subtree.
• Values larger than the current node go to the right subtree.

The insertion order matters because it determines the shape of the tree.

We are asked to count how many different reorderings of the array produce exactly the same BST structure as the original array. The original ordering itself should not be counted in the final answer, which is why we subtract one at the end.

For example:

nums = [3,4,5,1,2]

The BST formed is:

        3
       / \
      1   4
       \   \
        2   5

Any reordered array that inserts elements in a way that preserves this structure is valid.

The constraints are important:

• n <= 1000
• All elements are distinct
• The answer can become extremely large

Since n is up to 1000, brute force permutation generation is impossible because 1000! is astronomically large. We need a combinatorial counting strategy instead of explicitly generating permutations.

Several edge cases are important:

• Arrays that already form a completely skewed BST, such as [1,2,3,4]
• Very small arrays like [1] or [2,1]
• Balanced trees where many reorderings are possible
• Deep recursive partitions that could create large combinatorial counts

The problem guarantees all numbers are distinct, which simplifies BST construction because there are no duplicate-handling rules.

Approaches

Brute Force Approach

A brute force solution would generate every permutation of the array and check whether inserting that permutation into a BST produces the same tree structure as the original array.

The process would look like this:

1. Build the original BST from nums.
2. Generate all permutations of nums.
3. For each permutation:

• Build a BST.
• Compare it with the original BST.

4. Count matching permutations.
5. Subtract one to exclude the original ordering.

This approach is correct because it explicitly checks every possible ordering. However, it is completely infeasible.

For n = 1000, the number of permutations is:

1000!

which is far beyond any computable limit.

We need a way to count valid reorderings mathematically without enumerating them.

Key Insight

The crucial observation is that once the root is fixed, the relative ordering constraints become independent between the left and right subtrees.

Suppose the root is r.

• All values smaller than r must appear in the left subtree.
• All values larger than r must appear in the right subtree.

The left subtree elements can only affect the left subtree structure.

The right subtree elements can only affect the right subtree structure.

Therefore:

1. Recursively count valid reorderings for the left subtree.
2. Recursively count valid reorderings for the right subtree.
3. Count how many ways we can interleave the left and right subtree insertion sequences while preserving their internal relative orders.

That last part is a combinatorics problem.

If:

• Left subtree has L elements
• Right subtree has R elements

then the number of ways to interleave them is:

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

because we choose which positions belong to the left subtree.

The recursive formula becomes:

$f(nums)=\binom{L+R}{L}\times f(left)\times f(right)$

This transforms the problem into divide-and-conquer with combinatorics.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * n)	O(n)	Generates all permutations and rebuilds BSTs
Optimal	O(n²)	O(n²)	Recursive combinatorics with precomputed binomial coefficients

Algorithm Walkthrough

1. Precompute all binomial coefficients using Pascal's Triangle.

We need combinations repeatedly during recursion. Since n <= 1000, we can precompute:

$\binom{n}{k}$

for all valid n and k.

Pascal's identity is:

$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$

This allows efficient dynamic programming construction. 2. Define a recursive function.

The recursive function receives an array representing insertion order for a subtree. 3. Handle the base case.

If the subtree has fewer than 3 elements, there is only one valid ordering.

• Empty subtree
• Single node
• Root with one child

None of these cases allow alternative reorderings. 4. Split elements into left and right subtrees.

The first element is always the root.

Every smaller value goes into the left array.

Every larger value goes into the right array. 5. Recursively compute subtree counts.

Compute:

• Number of reorderings for left subtree
• Number of reorderings for right subtree

6. Compute interleaving count.

If the left subtree has L nodes and the right subtree has R nodes, we can merge them in:

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

ways while preserving internal ordering. 7. Multiply everything together.

Total ways:

$\binom{L+R}{L}\times leftWays\times rightWays$ 8. Return final answer minus one.

The recursion includes the original ordering itself, so subtract one before returning.

Why it works

The algorithm works because BST insertion depends only on relative ordering within each subtree.

Once the root is fixed:

• Left subtree values must remain in the same relative order to preserve the left subtree structure.
• Right subtree values must remain in the same relative order to preserve the right subtree structure.

The only freedom comes from interleaving left and right subtree insertions. The number of such interleavings is exactly the binomial coefficient. Since the left and right subtree constructions are independent, multiplying the counts gives the total number of valid reorderings.

Python Solution

from typing import List

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)

        # Precompute combinations using Pascal's Triangle
        comb = [[0] * (n + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            comb[i][0] = 1
            comb[i][i] = 1

        for i in range(2, n + 1):
            for j in range(1, i):
                comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD

        def count_ways(arr: List[int]) -> int:
            if len(arr) < 3:
                return 1

            root = arr[0]

            left_subtree = []
            right_subtree = []

            for value in arr[1:]:
                if value < root:
                    left_subtree.append(value)
                else:
                    right_subtree.append(value)

            left_ways = count_ways(left_subtree)
            right_ways = count_ways(right_subtree)

            left_size = len(left_subtree)
            right_size = len(right_subtree)

            interleavings = comb[left_size + right_size][left_size]

            return (
                interleavings
                * left_ways
                * right_ways
            ) % MOD

        return (count_ways(nums) - 1) % MOD

The implementation starts by precomputing binomial coefficients using Pascal's Triangle. This avoids recomputing combinations repeatedly during recursion.

The recursive helper function count_ways handles one subtree at a time. The first value becomes the root, and the remaining elements are partitioned into left and right subtree insertion sequences.

The recursion independently computes the number of valid reorderings for each subtree. Afterward, the code computes how many ways those subtree sequences can be interleaved while preserving their internal ordering.

Finally, the result subtracts one because the original ordering should not be counted.

Go Solution

package main

func numOfWays(nums []int) int {
	const MOD int = 1_000_000_007

	n := len(nums)

	// Precompute combinations
	comb := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		comb[i] = make([]int, n+1)
		comb[i][0] = 1
		comb[i][i] = 1
	}

	for i := 2; i <= n; i++ {
		for j := 1; j < i; j++ {
			comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD
		}
	}

	var countWays func([]int) int

	countWays = func(arr []int) int {
		if len(arr) < 3 {
			return 1
		}

		root := arr[0]

		left := []int{}
		right := []int{}

		for _, value := range arr[1:] {
			if value < root {
				left = append(left, value)
			} else {
				right = append(right, value)
			}
		}

		leftWays := countWays(left)
		rightWays := countWays(right)

		leftSize := len(left)
		rightSize := len(right)

		interleavings := comb[leftSize+rightSize][leftSize]

		result := int(
			(int64(interleavings) *
				int64(leftWays) %
				int64(MOD) *
				int64(rightWays)) % int64(MOD),
		)

		return result
	}

	return (countWays(nums) - 1 + MOD) % MOD
}

The Go implementation closely mirrors the Python version, but there are a few language-specific considerations.

Go integers can overflow during multiplication, so intermediate products are cast to int64 before applying modulo arithmetic.

Slices are used to represent subtree insertion orders. Since slices are dynamic, appending left and right subtree values is straightforward.

The subtraction at the end uses:

(countWays(nums) - 1 + MOD) % MOD

to avoid negative values after modular subtraction.

Worked Examples

Example 1

nums = [2,1,3]

BST:

    2
   / \
  1   3

Step 1: Root Partition

Root	Left	Right
2	[1]	[3]

Step 2: Recursive Counts

Subtree	Ways
[1]	1
[3]	1

Step 3: Interleavings

Left size = 1

Right size = 1

Ways to interleave:

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

Total:

2 × 1 × 1 = 2

Subtract original ordering:

2 - 1 = 1

Final answer:

1

Example 2

nums = [3,4,5,1,2]

Step 1: Root Partition

Root	Left	Right
3	[1,2]	[4,5]

Step 2: Left Subtree

[1,2]

Only one ordering.

Ways = 1

Step 3: Right Subtree

[4,5]

Only one ordering.

Ways = 1

Step 4: Interleavings

Left size = 2

Right size = 2

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

Total reorderings including original:

6 × 1 × 1 = 6

Exclude original:

6 - 1 = 5

Final answer:

5

Example 3

nums = [1,2,3]

BST:

1
 \
  2
   \
    3

Every insertion order that preserves this BST must begin with:

1,2,3

No alternative reorderings exist.

Result:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each recursive level partitions arrays, and combinations are precomputed in O(n²)
Space	O(n²)	Combination table dominates memory usage

The Pascal Triangle precomputation requires O(n²) time and space.

The recursive decomposition processes each node multiple times through array partitioning. In the worst case, such as a skewed BST, the recursive splitting costs:

n + (n-1) + (n-2) + ...

which equals O(n²).

The recursion stack itself can reach depth O(n) in the worst case.

Test Cases

from typing import List

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)

        comb = [[0] * (n + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            comb[i][0] = 1
            comb[i][i] = 1

        for i in range(2, n + 1):
            for j in range(1, i):
                comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD

        def count_ways(arr: List[int]) -> int:
            if len(arr) < 3:
                return 1

            root = arr[0]

            left = [x for x in arr[1:] if x < root]
            right = [x for x in arr[1:] if x > root]

            left_ways = count_ways(left)
            right_ways = count_ways(right)

            return (
                comb[len(left) + len(right)][len(left)]
                * left_ways
                * right_ways
            ) % MOD

        return (count_ways(nums) - 1) % MOD

sol = Solution()

assert sol.numOfWays([2,1,3]) == 1  # simple balanced BST
assert sol.numOfWays([3,4,5,1,2]) == 5  # mixed left/right structure
assert sol.numOfWays([1,2,3]) == 0  # completely skewed right tree
assert sol.numOfWays([3,2,1]) == 0  # completely skewed left tree
assert sol.numOfWays([2,1,3,4]) == 2  # extra node on right
assert sol.numOfWays([4,2,6,1,3,5,7]) == 79  # perfectly balanced BST
assert sol.numOfWays([1]) == 0  # single node
assert sol.numOfWays([2,1]) == 0  # two nodes
assert sol.numOfWays([3,1,2]) == 0  # only one valid ordering
assert sol.numOfWays([5,3,8,2,4,7,9]) > 0  # larger balanced tree

Test Summary

Test	Why
[2,1,3]	Small balanced BST
[3,4,5,1,2]	Mixed subtree interleavings
[1,2,3]	Completely right-skewed BST
[3,2,1]	Completely left-skewed BST
[2,1,3,4]	Uneven subtree sizes
[4,2,6,1,3,5,7]	Perfectly balanced BST with many reorderings
[1]	Minimum input size
[2,1]	Two-node tree
[3,1,2]	Limited valid reorderings
[5,3,8,2,4,7,9]	Larger balanced structure

Edge Cases

A completely skewed BST is one of the most important edge cases. Arrays like [1,2,3,4,5] create a tree where every node only has a right child. In this situation, there is only one valid insertion order. Any deviation changes the tree structure immediately. The implementation handles this naturally because one subtree is always empty, making the combination count equal to 1 at every recursive level.

Very small arrays are another common source of bugs. Arrays with length 1 or 2 cannot produce alternative reorderings. The recursive base case:

if len(arr) < 3:
    return 1

correctly handles these scenarios by recognizing that there is only one possible ordering for such tiny trees.

Balanced BSTs create extremely large combinatorial counts. For example, a perfectly balanced tree with many nodes can generate enormous numbers of valid reorderings. Without modular arithmetic, integer overflow would occur. Both implementations apply modulo 10^9 + 7 throughout all computations to keep values bounded.

Another subtle edge case is modular subtraction. Since we subtract one at the end to exclude the original ordering, the result could become negative if not handled carefully. The Go implementation explicitly adds MOD before applying % MOD to guarantee a non-negative result.