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 lar

maxProduct.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxProduct = function(root) {
    const MOD = 1_000_000_007;

    // ---------------------------------------------
    // First pass: compute total sum of the tree
    // ---------------------------------------------
    function getTotalSum(node) {
        if (!node) return 0;
        return node.val + getTotalSum(node.left) + getTotalSum(node.right);
    }

    const totalSum = getTotalSum(root);

    // ---------------------------------------------
    // Second pass: compute subtree sums AND
    // track the best product we can form
    // ---------------------------------------------
    let maxProductValue = 0;

    function computeSubtreeSum(node) {
        if (!node) return 0;

        // Sum of this subtree
        const left = computeSubtreeSum(node.left);
        const right = computeSubtreeSum(node.right);
        const subtreeSum = node.val + left + right;

        // Product if we cut above this subtree
        const product = subtreeSum * (totalSum - subtreeSum);

        // Track the maximum product (before mod)
        if (product > maxProductValue) {
            maxProductValue = product;
        }

        return subtreeSum;
    }

    computeSubtreeSum(root);

    // ---------------------------------------------
    // Return the result modulo 1e9+7
    // ---------------------------------------------
    return maxProductValue % MOD;
};