Clear Explanation of an Easy Recursive Combinatorics Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nAs with most tree problems, we repeatedly explore the left and right subtrees of the tr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs with most tree problems, we repeatedly explore the left and right subtrees of the tree to arrive at our solution. In this case, we look at how many permutations of a subtree array correspond to the same subtree.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAfter noting that the first element in the array is the root of the (sub)tree, we can also conclude that all the elements in num[1:] which are smaller than the root will be in the left subtree and all the elements in nums[1:] which are greater than the root will be in the right subtree. \n\nFor example, if the BST array is [3, 2, 1, 4, 5], then the root is 3 and the left subtree is [2, 1] with root node 2 and the right subtree is [4, 5] with root node 4. Notice that the subarray [2, 3] can be permuted in any position in nums[1:] as along as their relative permutation to each other is the same. For example, the array [3, 4, 2, 5, 1] will also give us the left subtree [2, 1] and the right subtree [4, 5]. Let $m$ be the length of the array, and let $k$ be the number of nodes in the left subtree. We need to choose $k$ spots out of $m-1$ positions to place our left subtree nodes in the array. This can done in $\\binom{m-1}{k}$ ways where $\\binom{x}{y}$ is the binomial coefficient which is equal to  $\\frac{x!}{y!(x-y!)}$. \n\nHowever, our final answer is not $\\binom{m-1}{k}$. This only tells us the number of ways the children of the current root node can be permuted in the array. It does not tell us about the children nodes of the current root node\'s children i.e. it does not tell us about deeper subtrees. For example, consider the BST array [3, 1, 5, 2, 4, 7]. The left subtree here is [1, 2] and the right subtree is [5, 4, 7]. Notice how the right subtree can be [5, 7, 4] or [5, 4, 7] and still correspond to the same BST. This implies that we must traverse each subtree and calculate the valid permutations for its children node as well. The final answer will be the valid permutation of the left subtree multiplied by the valid permutations of the right subtree multiplied by the valid permutations of the current tree. \n\n# Complexity\n- Time complexity: $O(n^2)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThis is because we are calling the dfs function twice for each node in the tree. \n\n- Space complexity:$O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nFirst, we are storing the left and right subtrees which have linear space. Next, our recursive call stack can have at most $n-1$ calls.\n\n# Code\n```\n\nclass Solution:\n\tdef numOfWays(self, nums: List[int]) -> int:\n\t\t"""\n\t\tCalculates the number of ways an array can be rearranged and\n\t\tstill correspond to the same BST. \n\n\t\tArgs:\n\t\t\tnums: List[int] = array of integers which correspond to a BST \n\n\t\tReturns:\n\t\t\tcount: int = number of ways the array can be rearranged and \n\t\t\t\t\t\t still correspond to the same BST\n\t\t"""\n\n\t\t# Since the answer might be very large, we return it modulo 10**9 + 7\n\t\tmod = 10 ** 9 + 7 \n\n\t\t# define a recursive function which repeatedly calculates the answer\n\t\t# for each level of the binary search tree\n\n\t\tdef dfs(arr):\n\n\t\t\t# if the length of the current subtree is less than or equal to\n\t\t\t# two, then we can\'t rearrange the array in more ways since the \n\t\t\t# first element is the root of the subtree\n\n\t\t\tlength = len(arr)\n\t\t\tif length <= 2:\n\t\t\t\treturn 1 \n\n\t\t\t# we collect the array representation of the left subtree and the\n\t\t\t# right subtree\n\t\t\tleft_nodes = [num for num in arr if num < arr[0]]\n\t\t\tright_nodes = [num for num in arr if num > arr[0]]\n\n\t\t\t# at this current level, we can permute the left and right subtree\n\t\t\t# nodes by choosing len(left_nodes) spots from the arr[1:]\n\t\t\tcurrent_level_permutation = comb(length-1, len(left_nodes))\n\n\t\t\t# we have calculated the permutations for the current level of the BST,\n\t\t\t# we need to calculate the permutations for the left subtree and the right\n\t\t\t# subtree. We multiply all the factors together and return the final answer.\n\t\t\treturn dfs(left_nodes) * dfs(right_nodes) *current_level_permutation\n\n\t\t# we call the function for the BST, subtract one since the argument passed in is\n\t\t# not considered, and return the answer modulo 10 ** 9 + 7\n\t\treturn (dfs(nums) - 1) % mod  \n```
['Tree', 'Recursion', 'Combinatorics', 'Python3']