[Python] O(n^2) post-order traversal
Idea\nThe key idea is to maintain the topological order of the BST. \nMore specifically, this solution works in this way. \n\nStep 1\nFor every node, given that
## Idea\nThe key idea is to maintain the topological order of the BST. \nMore specifically, this solution works in this way. \n\n**Step 1**\nFor every node, given that its left subtree has `L` children and its right subtree has `R` children. We denote the number of way to schedule the placement of `L + R` nodes as `N(L, R)`. We then have the following relation.\n- `N(L, R) = N(L - 1, R) + N(L, R - 1)`, if we want to place 2 subtrees simultaneously, we can place one element either from the left, or from the right.\n- `N(L, 0) = 1` and `N(0, R) = 1`, if we only have one subtree to place, we have only 1 option, that is to place this subtree directly.\n\n**Step 2**\nWe then compute the product of all `N` values for all the nodes.\n\nPlease leave an upvote if you like my post. It means a lot to me.\n\n## Complexity\n- Time and Space: `O(n^2)`\n\n## Python\n```\nfrom functools import lru_cache\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n        @lru_cache(None)\n        def combine(x, y):\n            if x == 0 or y == 0: return 1\n            return combine(x, y - 1) + combine(x - 1, y)\n        \n        bst = TreeNode(nums[0])\n        for n in nums[1:]:\n            bst.add(n)\n        \n        res = 1\n        def traverse(root):\n            nonlocal res\n            if not root: return 0\n            lc = traverse(root.left)\n            rc = traverse(root.right)\n            res = res * combine(lc, rc) % 1000000007\n            return lc + rc + 1\n        traverse(bst)\n        \n        return res - 1\n        \nclass TreeNode:\n    def __init__(self, v):\n        self.val = v\n        self.left = None\n        self.right = None\n        \n    def add(self, v):        \n        curr = self\n        node = TreeNode(v)\n        while 1:\n            if v < curr.val:\n                if not curr.left:\n                    curr.left = node\n                    break\n                curr = curr.left\n            else:                \n                if not curr.right:\n                    curr.right = node\n                    break\n                curr = curr.right\n```
[]