Problem Statement in English

You’re given the root of a binary tree. Split the binary tree into two subtrees by removing one edge such that the product of the sums of the subtrees is maximized.

Return the maximum product of the sums of the two subtrees.

Since the answer may be too large, return it modulo 10^9 + 7, but only after finding the maximum product not before.

Approach

To solve this problem, we don’t really need to split the tree physically. Instead, we can calculate the sum of all nodes in the tree first.

Then, we can explore each subtree and calculate the potential product of splitting at that subtree.

You can either do this by traversing the tree twice (once to get the total sum and once to calculate products) or do it in a single traversal by storing subtree sums.

I chose the latter, and it gave me a really nice beats%.

Solution in Python


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        MOD = 10**9+7
        options = []

        # find overall sum of tree
        def dfs(node):
            s = node.val

            if node.left:
                s += dfs(node.left)
            if node.right:
                s += dfs(node.right)

            options.append(s)

            return s

        osum = dfs(root)
        best = 0

        # then all options and do ((overall - option) * (option)) % MOD
        for option in options:
            best = max(best, ((osum - option) * option))

        return best % MOD

Complexity

  • Time: $O(n)$
    We visit each node once to calculate the sum of the tree and store subtree sums.

  • Space: $O(n)$
    Since we are storing the sum of each subtree in the options list.

And we are done.