We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Product of Splitted Binary Tree

Difficulty: Medium

Problem Description

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. Note that you need to maximize the answer before taking the mod and not after taking it.

Key Insights

  • The maximum product can be achieved by splitting the tree at an edge.
  • The sum of the entire tree can be computed first.
  • For each subtree formed by removing an edge, calculate the product of the sum of that subtree and the sum of the remaining tree.
  • The problem can be solved using Depth-First Search (DFS) to traverse the tree and compute the sums.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree since we visit each node once. Space Complexity: O(H), where H is the height of the tree due to the recursion stack.

Solution

To solve this problem, we can use a Depth-First Search (DFS) approach. First, we compute the total sum of the tree. Then, we can traverse the tree again to find the sum of each subtree formed by removing an edge. By keeping track of the maximum product of the sums of the two resulting subtrees, we can find the answer.

  1. Compute the total sum of the tree.
  2. Use DFS to find the sum of each subtree and calculate the product of the subtree's sum and the remaining tree's sum.
  3. Update the maximum product found during the traversal.

Code Solutions

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: TreeNode) -> int:
        MOD = 10**9 + 7

        # Helper function to calculate the total sum of the tree
        def total_sum(node):
            if not node:
                return 0
            return node.val + total_sum(node.left) + total_sum(node.right)

        # Helper function to calculate the max product
        def max_product(node):
            if not node:
                return 0
            left_sum = max_product(node.left)
            right_sum = max_product(node.right)
            # Calculate the product with the remaining tree
            nonlocal max_prod
            current_sum = left_sum + right_sum + node.val
            max_prod = max(max_prod, (total - current_sum) * current_sum)
            return current_sum

        total = total_sum(root)
        max_prod = 0
        max_product(root)
        return max_prod % MOD
← Back to All Questions