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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Product of Splitted Binary Tree

Number: 1465

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft

Problem Description

Given the root of a binary tree, split the tree into two subtrees by removing exactly one edge such that the product of the sums of the nodes in the resulting subtrees is maximized. Return the maximum possible product of these sums modulo 10^9 + 7.

Key Insights

  • We need to maximize the expression: subtree_sum * (total_sum - subtree_sum) for any valid subtree split.
  • A two-pass approach is effective: first, compute the total sum of the tree; second, use a DFS to compute the sum for each subtree and consider removing the edge leading to that subtree.
  • The use of DFS (post-order traversal) allows us to calculate subtree sums in one go.
  • Taking the modulo (10^9 + 7) only at the final step, as the intermediate values may be large.
  • Edge removal effectively splits the tree at every possible subtree; the maximum product found during traversal is the answer.

Space and Time Complexity

Time Complexity: O(n) because each node in the tree is visited once during the DFS. Space Complexity: O(h) due to the recursion stack, where h is the height of the tree.

Solution

The solution uses a Depth-First Search (DFS) approach with two passes:

  1. In the first pass, a DFS is used to calculate the total sum of all nodes in the tree.
  2. In the second DFS, for each node, the sum of the subtree rooted at that node is computed. For each such node, if you remove the edge from its parent, you effectively split the tree into two parts: one with the current subtree sum and the other with (total sum - current subtree sum). Calculate the product for this split and track the maximum product encountered.
  3. Return the maximum product modulo 10^9 + 7.

This approach efficiently leverages recursion and a simple arithmetic observation to arrive at the solution.

Code Solutions

# 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: TreeNode) -> int:
        mod = 10**9 + 7
        
        # First DFS pass: Compute the total sum of the tree.
        def computeTotalSum(node):
            if not node:
                return 0
            left_sum = computeTotalSum(node.left)
            right_sum = computeTotalSum(node.right)
            return node.val + left_sum + right_sum
        
        total_sum = computeTotalSum(root)
        max_product = 0
        
        # Second DFS pass: Calculate the sum of each subtree and update max product.
        def maxProductDFS(node):
            nonlocal max_product
            if not node:
                return 0
            left_subtree = maxProductDFS(node.left)
            right_subtree = maxProductDFS(node.right)
            subtree_sum = node.val + left_subtree + right_subtree
            
            # Calculate the product if we split the tree at this node's edge.
            product = subtree_sum * (total_sum - subtree_sum)
            if product > max_product:
                max_product = product
            return subtree_sum
        
        maxProductDFS(root)
        return max_product % mod
← Back to All Questions