C++/Python. Question explained. Then detailed solution. Short. Fast. Readable.
Question can seem confusing. Note that we are inserting the numbers in the binary search tree in exactly the same order as they occur in the input array. \n\nTh
Question can seem confusing. Note that we are inserting the numbers in the binary search tree in *exactly the same order as they occur in the input array*. \n\nThis is a good time to recall a fact which may seem very obvious but is crucial to understand the question: *For a fixed sequence of insertion, the number of binary search trees generated is exactly one.*\n\n### Approach\n\nKey insight:  as long as the root of the binary search tree is inserted first (and recursively, other parents are inserted before their subtrees), any permutation of other elements will generate the same BST. This may feel a bit mouthful, so let\'s understand with an example.\n\nFor BST given in example, as long as 3 comes before others, 4 comes before 5, 1 comes before 2, we can generate the same BST.\n![image](https://assets.leetcode.com/users/images/c450a9aa-7b50-4fe4-b041-f1f4328c957c_1598773056.857656.png)\n\nThis is true for all of the following arrays:\n```python\n[3,1,2,4,5]\n[3,1,4,2,5]\n[3,1,4,5,2]\n[3,4,1,2,5]\n[3,4,1,5,2]\n```\nLet\'s see an example of [3, 4, 1, 5, 2]\n\nFirst to insert is 3. Tree is just a single node 3.\n\nThen we insert 4. Has to go on right of 3. Tree is\n```\n    3\n\t \\\n\t  4\n```\n\nThen we insert 1. (Again note that we have to insert in the same order as input array. I\'ll repeat this several times :D)\n\n```\n      3\n\t / \\\n\t1  4\n```\n\nThen 5\n```\n       3\n\t  / \\\n\t1   4\n\t      \\\n\t\t   5\n```\n\nThen 2\n\n```\n       3\n\t  / \\\n\t1   4\n  \t \\     \\\n\t  2\t   5\n```\n\nTry other arrays listed above and convince yourself that it will generate identical BST.\n\nSo, for this BST, \n\n- choose 3 as root (the element which is first in insertion order)\n- `[1,2]` will be in the `left` subtree. Maintaining order is important to ensure that we generate the same BST.  Let `m = left.size()`\n- `[4,5]` in `right` subtree. Let `n = right.size()`\n- find ways to interleave them.\nThe number of ways are just interleavings of left and right.  Similar to https://leetcode.com/problems/interleaving-string/\nHow many ways are there to interleave left and right?\n\nThere are `m + n` total positions. If we put `m` elements from `left` in randomly chosen `m` positions (but, in order), we can put the rest in other (right ;-)) positions. (Equivalently, we could also have chosen to fill `n` arbitrary positions from `right` and fill remaining from whatever positions are left.)\n\nThat\u2019s just:\n![image](https://assets.leetcode.com/users/images/7e8c309e-7a08-49a7-a86e-8e3600ec8a95_1598774425.5294194.png)\n\n\nSo algorithm would be\n\n- Fix the root (first element of the input)\n- Find smaller and larger elements than root. These would be left and right subtrees (meh)\n- Combine, which is an interleaving as explained above.\n\nFollow up: If you actually want to [generate all the arrays](https://stackoverflow.com/questions/21211701/given-a-bst-and-its-root-print-all-sequences-of-nodes-which-give-rise-to-the-sa/24398114#24398114)\n\n### Python\n```python\nclass Solution:\n\n    def numOfWays(self, numbers):\n        mod = 10 ** 9 + 7\n\n        def ways_to_interleave(sequence_1, sequence_2):\n            """\n            Number of ways to interleave two sequences (i.e. maintaining the order)\n            """\n            total_things = len(sequence_1) + len(sequence_2)\n            things_to_choose = len(sequence_1)  # or len(sequence_2), doesn\'t matter.\n            return math.comb(total_things, things_to_choose)\n\n        def helper(subsequence):\n            if not subsequence:\n                return 1\n            root_value = subsequence[0]\n            left = [number for number in subsequence if number < root_value]\n            right = [number for number in subsequence if number > root_value]\n            ways_to_arrange_left = helper(left)\n            ways_to_arrange_right = helper(right)\n            return ways_to_arrange_left * ways_to_arrange_right * ways_to_interleave(left, right)\n        return (helper(numbers) - 1) % mod\n\n```\nThis surprisingly beats all other python solutions so far (but speed is not the aim of this code, it\'s readability)\n\n### C++\n\nPeople who build numerical libraries have my huge respect. Getting [`combinations` method (ommitted) without overflow is tricky for a C++ noob like me. I\'ve lifted the version from here](https://stackoverflow.com/questions/11809502/which-is-better-way-to-calculate-ncr?noredirect=1&lq=1). Others have used pascal triangle methods, which are easiest to implement in interview and worth a look.\n\n```cpp\n#include <vector>\n#include <cmath>\n#include <algorithm>\n\nclass Solution {\npublic:\n    int numOfWays(std::vector<int>& numbers) {\n\t\t\treturn (helper(numbers) - 1) % mod;\n    }\n\nprivate:\n\t\tint mod = std::pow(10, 9) + 7;\n\n\t\tint ways_to_interleave(int sequence_1_length, int sequence_2_length) {\n\t\t\treturn combinations(sequence_1_length + sequence_2_length, sequence_2_length, mod); // combinations function is omitted as it\'s not really relevant to core issue of the question.\n\t\t}\n\n\t\tlong helper(const std::vector<int>& numbers) {\n\t\t\tif (numbers.empty()) {\n\t\t\t\treturn 1;\n\t\t\t}\n\t\t\tint root_value = numbers[0];\n\t\t\tstd::vector<int> left, right;\n\t\t\tstd::copy_if(numbers.begin(), numbers.end(), std::back_inserter(left), [root_value](int number){return number < root_value;});\n\t\t\tstd::copy_if(numbers.begin(), numbers.end(), std::back_inserter(right), [root_value](int number){return number > root_value;});\n\t\t\tlong  ways_to_arrange_left = helper(left) % mod;\n\t\t\tlong ways_to_arrange_right = helper(right) % mod;\n            long duck_this = (ways_to_arrange_left * ways_to_arrange_right) % mod;\n\t\t\tlong duck_this_too = (duck_this * ways_to_interleave(left.size(), right.size())) % mod;\n            return duck_this_too;\n\t\t\t\t\t}\n};\n```
['C', 'Python']