Insertion Orders Producing the Same BST
A configuration is loaded by inserting keys into a BST in some order. Given one insertion order, count how many other orders build the exact same tree shape — useful for de-duplicating equivalent deploy sequences.
Problem
Given an array nums that is a permutation of 1..n, inserting its values left to right into an initially empty BST yields a tree. Return the number of different insertion orders of the same values that produce an identical BST, excluding the given order itself. Return the count modulo 1e9 + 7.
Input
An array nums, a permutation of 1..n.
Output
An integer: the number of other valid orders modulo 1e9 + 7.
Constraints
- 1 <= nums.length <= 1000
- nums is a permutation of 1..nums.length.
Examples
Example 1
Input
nums = [2,1,3]
Output
1
Only [2,3,1] also builds the same BST; that is 1 other order.
Example 2
Input
nums = [3,4,5,1,2]
Output
5
Five other orders produce the same tree.