1339. Maximum Product of Splitted Binary Tree

Time: O(n)

Space: O(n)

Intuition

For each edge removal, the product of two subtree sums. One subtree = subtree sum S, other = total - S. Maximize S * (total - S).

Algorithm

1Compute total sum. DFS to compute subtree sums.
2For each subtree sum S: compute S * (total - S). Track maximum.

Common Pitfalls

•Answer can be very large — return result modulo 10^9+7. Compute subtree sums in post-order DFS.

1339.cs

// Approach: Two DFS passes; first computes total sum; second finds the subtree sum whose product with the remainder is maximised.
// Time: O(n) Space: O(n)

// Definition for a binary tree node.
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public int MaxProduct(TreeNode root)
    {
        const int MOD = 1000000007;
        long ans = 0;
        List<int> allSums = new List<int>();
        long totalSum = TreeSum(root, allSums);

        foreach (long sum in allSums)
            ans = Math.Max(ans, sum * (totalSum - sum));

        return (int)(ans % MOD);
    }

    private int TreeSum(TreeNode root, List<int> allSums)
    {
        if (root == null)
            return 0;

        int leftSum = TreeSum(root.left, allSums);
        int rightSum = TreeSum(root.right, allSums);
        int sum = root.val + leftSum + rightSum;

        allSums.Add(sum);
        return sum;
    }
}

Was this solution helpful?