Introduction

In this blog post, we will explore how to solve the LeetCode problem "1339" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 1: 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 (1110) Example 2: Input: root = [1,null,2,3,4,null,null,5,6] Output: 90 Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (156) Constraints: The number of nodes in the tree is in the range [2, 5 * 104]. 1 <= Node.val <= 104

Explanation

Here's the breakdown of the solution:

• Calculate Total Sum: First, traverse the entire tree to calculate the total sum of all nodes. This will be used to determine the sum of the other subtree when an edge is removed.
• DFS for Subtree Sums: Perform a Depth-First Search (DFS) to calculate the sum of each subtree rooted at every node. During this DFS, for each node, compute the product of the subtree sum and the remaining tree sum (total sum - subtree sum). Keep track of the maximum product encountered.

• Modulo Operation: Apply the modulo operator (10⁹ + 7) only at the very end, after finding the maximum product to avoid inaccuracies.

• Runtime & Storage Complexity: O(N) runtime, O(N) storage where N is the number of nodes in the tree.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxProduct(root: TreeNode) -> int:
    total_sum = 0
    subtree_sums = []

    def calculate_total_sum(node):
        nonlocal total_sum
        if not node:
            return 0
        calculate_total_sum(node.left)
        calculate_total_sum(node.right)
        total_sum += node.val

    calculate_total_sum(root)

    max_product = 0
    MOD = 10**9 + 7

    def calculate_subtree_sum(node):
        nonlocal max_product
        if not node:
            return 0

        left_sum = calculate_subtree_sum(node.left)
        right_sum = calculate_subtree_sum(node.right)

        subtree_sum = node.val + left_sum + right_sum
        product = (total_sum - subtree_sum) * subtree_sum
        max_product = max(max_product, product)
        subtree_sums.append(subtree_sum)

        return subtree_sum

    calculate_subtree_sum(root)

    return max_product % MOD