Maximum Product Of Splitted Binary Tree - Leetcode Solution

Problem Statement:

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 109 + 7.

Note that you need to maximize the answer before taking the mod and not after taking it.

Example:

Input: root = [1,2,3,4,5,6] Output: 110

Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

Solution:

First we need to find the sum of the entire binary tree.

Then we need to do a post-order traversal of the binary tree and for each node we need to find the sum of the subtree rooted at that node.

Then we can calculate the maximum product of the sums of the two subtrees by traversing the binary tree again. For each node, we can calculate the product of the sum of its left subtree and the sum of its right subtree and update the maximum product seen so far.

Finally, we return the maximum product modulo 109 + 7.

Here is the Python implementation of the solution:

class Solution: def maxProduct(self, root: Optional[TreeNode]) -> int: self.total_sum = 0

    # Find the sum of the entire binary tree
    def find_sum(root):
        if not root:
            return 0

        left_sum = find_sum(root.left)
        right_sum = find_sum(root.right)

        self.total_sum += root.val + left_sum + right_sum

        return root.val + left_sum + right_sum

    # Find the sum of the subtree rooted at each node
    def find_subtree_sum(root):
        if not root:
            return 0

        left_sum = find_subtree_sum(root.left)
        right_sum = find_subtree_sum(root.right)

        root.subtree_sum = root.val + left_sum + right_sum

        return root.subtree_sum

    find_sum(root)
    find_subtree_sum(root)

    max_product = 0

    # Calculate the maximum product of the sums of the subtrees
    def find_max_product(root):
        nonlocal max_product

        if not root:
            return 0

        left_sum = find_max_product(root.left)
        right_sum = find_max_product(root.right)

        product = left_sum * (self.total_sum - left_sum) if left_sum else 0
        product = max(product, right_sum * (self.total_sum - right_sum) if right_sum else 0)
        product = max(product, max_product)

        return root.subtree_sum

    find_max_product(root)

    return max_product % (10**9 + 7)

1