order. The first number becomes the root; each next number walks down from the root, going left when it is smaller than the current node and right when it is larger, until it finds a free spot.
How many **other** insertion orders of the same numbers produce exactly the same tree? The original order itself does not count. The answer can be large, so return it modulo 10⁹ + 7.order=[2, 3, 1] → 1
The root is 2 with children 1 and 3. Only the order [2, 1, 3] gives the same tree.
order=[4, 2, 1, 3, 5] → 7
4 must come first, 2 must come before 1 and 3, and 5 can go anywhere after 4. That makes 8 orders, or 7 without the original.
order=[3, 2, 1] → 0
The tree is a chain, every key must follow the previous one, so there are no other orders.
len(order) ≤ 1000order[i] ≤ 10⁵order are distinctorder=[2, 3, 1]
1
Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.