Detailed Explanation | (Hopefully) Easy to understand | Python Solution
Intuition and Approach\n Describe your first thoughts on how to solve this problem. \nLet\'s start small\n\nLook at this Binary Search Tree\n\n   2\n  / \\\n 1 
# Intuition and Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet\'s start small\n\nLook at this Binary Search Tree\n```\n   2\n  / \\\n 1   3\n```\nWhat do you think is the valid array to form this BST?\n`[2,1,3]` and `[2,3,1]` both are correct here.\n\nLet\'s look at another BST\n```\n   6\n  / \\\n 5   7\n```\nWhat do you think is the valid array to form this tree?\nI guess, you got it right - `[6,5,7]` and `[6,7,5]`.\n\nWhat **observations** have you concluded from the above two examples?(I strongly suggest you to think, before you move ahead)\n-> The **root** is always **first** (This is our **Observation #1**)\n-> Also, if nodes are on the same level, their relative ordering does not matter (**Obs #2**)\n\nLet\'s take a look at a bigger BST\n```\n        4 \n     /    \\\n    2      6\n  /  \\    /  \\\n 1    3  5    7\n```\nWhat do you think is the valid array to form this tree?\n\nThis Might look difficult at first. But if we properly **observe**, we can use the above two examples to get some solution here.\n\nUsing Observation #1, 4 will be the first element.\n\nLet\'s break down the problem to left and right subtree. Since, it is a BST all the elements smaller than root will be on the left subtree and vice versa.\n\nUsing Obs #2, the relative order of `1,3,5,7` won\'t matter. But from Obs #1, `1,3` has to be **after** `2` and `5,7` has to be **after** `6`. And similarly, the relative order of `2` and `6` won\'t matter.\n\nSo, how do we get the permutations of subtrees?\n\n****\n**Before moving down further, I highly encourage to solve these Problems first to get the grasp of what is coming ahead:**\n1. [Permutations](https://leetcode.com/problems/permutations/description/)\n2. [Permutations II](https://leetcode.com/problems/permutations-ii/)\n3. [Permutations of a String](https://leetcode.com/problems/permutation-in-string/description/) (Optional)\n****\n\n$$Continuing....$$\nSo, how do we get the permutations of subtrees?\nTo tackle this problem let\'s mark left subtree nodes as **0** and right subtree nodes as **1**. Because with that, the relative ordering of the subtree will stay the same.\n\nFor example, `[2,1,3,6,5,7]` = `[0,0,0,1,1,1]`. Now if we generate different permutations of this, let\'s say `[1,0,1,0,1,0]`, we can unmark zeros and ones with the respective subtree values i.e., `[6,2,5,1,7,5]`. Observe that the relative order of subtree nodes remains intact.\n\nNow, the permutation [6,2,5,**1**,7,**5**] and [6,2,5,**5**,7,**1**] (Obeserve postiion of `1` and `5`) both are correct, but since we repalce them with **0s** and **1s** both of them are considered same only. To get that value, we follow the same process on the subtree as well i.e.,\n`[1,5]` = `[0,1]` (left subtree as **0** and right as **1**). Which generates 2 permutations.\n\nThis part -- `[2,1,3,6,5,7]` = `[0,0,0,1,1,1]` -- will generate `(6!/(3! * 3!))` permutations (For proof - You can try this on a smaller number say, `[0,0,1,1]`). \n\nWell, how is the above formula concluded? You can think of it as chosing 3 places from 6 available places (`6 C 3`) (Or formula of permutations having duplicate values). Also, to note that we also have to get the permutations of the subtree, so we multiply it with permutations of subtrees.\n\nSo, it will become `(6!/(3! * 3!)) * 2! * 2!` (`2!` for left and `2!` for permutations of right subtree)\n\nHence, we keep on doing the same recursively for all subtrees and multiply their corresponding permutations.\n\n# Code\n```\nclass Solution:\n    def numOfWays(self, numList: List[int]) -> int:\n        def find_no_of_combinations_of(nums):\n            # having a single num has just 1! permutations\n            if len(nums) < 2:\n                return 1\n            # get the left subtree\n            left_subtree = [num for num in nums if num < nums[0]]  \n            # get the right subtree\n            right_subtree = [num for num in nums if num > nums[0]]\n            \n            # The (6!/ (3! * 3!)) * 2! * 2! step\n            return (comb(len(left_subtree) + len(right_subtree), len(left_subtree)) *\\\n                    find_no_of_combinations_of(left_subtree) *\\\n                    find_no_of_combinations_of(right_subtree)) % (10**9 + 7)\n        \n        # at last we minus 1 because our ans permutations \n        # has the permutation from the question as well\n        return find_no_of_combinations_of(numList) - 1\n\n            \n```
['Binary Search Tree', 'Combinatorics', 'Binary Tree', 'Python3']