Finding topological sorts (clean code + explanation)
Intuition\nThis problem can be rephrased as finding the number of ways to topological sort the BST. We are given one, which can be used to build a tree, and the
# Intuition\nThis problem can be rephrased as finding the number of ways to topological sort the BST. We are given one, which can be used to build a tree, and the task is to find the rest.\n\n# Approach\nAfter building our tree, define a helper function `h(x)` that returns the number of topological sortings for the tree node `x`. If number of nodes in the subtree `x` is less than or equal to 1, then `h(x) = 1` (Base case).\n\nFor an arbitrary tree node, the goal is to work out how many ways there are of interleaving the topological sorts of the left and right subtrees. For the time being, lets assume that both the left and right subtrees have exactly one topological sort each, and lengths `m` and `n` respectively (like example 2 in the problem where `x` is the root). Assume these sequences are $l=(l_1, l_2, ..., l_m)$ and $r=(r_1, r_2, ..., r_n)$.\n\nWe know the total length of the ordering is $m + n$, and if we can figure out where all of the values from $l$ go, those for $r$ will fall out. In other words, we need to choose $m$ indices from $m + n$; therefore the answer is $\\frac{(m + n)!}{m! n!}$ (combination formula).\n\nWhen there are more than 1 topological sorts for each subtree, we have to multiply the above formula by the product of these values (since the orderings are independent of each other... different subtrees):\n$$ \\frac{(m +n)!}{m!n!}\\times h(x_{left}) \\times h(x_{right}) $$.\n\n# Code\n```\nclass Node:\n    def __init__(self, val):\n        self.val = val\n        self.left = None\n        self.right = None\n        self.size = 1\n\n    def insert(self, x):\n        self.size += 1\n        if x < self.val:\n            if self.left: self.left.insert(x)\n            else: self.left = Node(x)\n        else:\n            if self.right: self.right.insert(x)\n            else: self.right = Node(x)\n\n\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n        root = Node(nums[0])\n        for i in range(1, len(nums)):\n            # Insert\n            root.insert(nums[i])\n\n        # Return num topsorts\n        def h(root):\n            if not node or (not root.left and not root.right): return 1\n            L = h(root.left)\n            R = h(root.right)\n            return math.comb(root.size - 1, root.left.size if root.left else 0) * L * R\n\n        return (h(root) - 1) % 1_000_000_007\n\n```\n\n# References\n\n- https://cs.stackexchange.com/questions/12713/find-the-number-of-topological-sorts-in-a-tree\n- https://cs.stackexchange.com/questions/12713/find-the-number-of-topological-sorts-in-a-tree
['Math', 'Tree', 'Recursion', 'Combinatorics', 'Python3']