Problem statement

https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/

Solution

The idea is to use recursion, where we look at part which should be to the left and to the right. Then we use combinatorics to calculate number of options.

Complexity

Time complexity is O(n^2), space is potentially O(n).

Code

class Solution:
    def numOfWays(self, nums):
        def dfs(A):
            if not A: return 1
            lft = [i for i in A[1:] if i > A[0]]
            rgh = [i for i in A[1:] if i < A[0]]
            return dfs(lft) * dfs(rgh) * comb(len(A) - 1, len(lft)) % (10**9 + 7)

        return dfs(nums) - 1

Remark

I think there is a way to do it in O(n log n) as well, but we need to be able to quilckly create our BST, because it given in not obvious way.