BinarySearch 1036 Ways to Remove Leaves of a Tree

Problem statement

https://binarysearch.com/problems/Ways-to-Remove-Leaves-of-a-Tree/

Solution

If we have L nodes for the left subtree and R nodes for the right subtree, then we have $C_{L+R}^L$ ways to delete them and then use recursion. Also I suprised that number of ways is small enough, it means tests are not very strong.

Complexity

It is O(n) for time and space.

Code

MOD, M = 10**9 + 7, 10**5
F = [1]*(M+1)
for i in range(1, M+1):
    F[i] = (F[i-1] * i) % MOD

I = [1]*M + [pow(F[M], MOD - 2, MOD)]
for i in range(M-1, 0, -1):
    I[i] = I[i+1]*(i+1) % MOD

class Solution:
    def solve(self, root):
        def dfs(node):
            if not node: return (0, 1)
            L, lft = dfs(node.left)
            R, rgh = dfs(node.right)
            return L + R + 1, (lft * rgh * F[L + R]*I[L]*I[R]) % MOD
        return dfs(root)[1]