Maximum Product of Splitted Binary Tree

medium tree dfs

Problem

Given the root of a binary tree, remove one edge to split it into two subtrees so that the product of their sums is maximized. Return the maximum product modulo 10⁹ + 7.

Inputroot = [1,2,3,4,5,6]

Output110

Total = 21. Best cut leaves subtree sums 11 and 10 → 110.

tree (level-order, # = null)

def max_product(root):
    MOD = 10**9 + 7
    sums = []
    def total(n):
        if not n: return 0
        s = n.val + total(n.left) + total(n.right)
        sums.append(s)
        return s
    T = total(root)
    best = max(s * (T - s) for s in sums)
    return best % MOD

function maxProduct(root) {
  const MOD = 1000000007n;
  const sums = [];
  function total(n) {
    if (!n) return 0;
    const s = n.val + total(n.left) + total(n.right);
    sums.push(s);
    return s;
  }
  const T = total(root);
  let best = 0n;
  for (const s of sums) {
    const p = BigInt(s) * BigInt(T - s);
    if (p > best) best = p;
  }
  return Number(best % MOD);
}

class Solution {
    long T = 0; long best = 0;
    long total(TreeNode n) {
        if (n == null) return 0;
        long s = n.val + total(n.left) + total(n.right);
        best = Math.max(best, s * (T - s));
        return s;
    }
    public int maxProduct(TreeNode root) {
        T = total(root);
        best = 0;
        total(root);
        return (int)(best % 1000000007L);
    }
}

class Solution {
public:
    long long T = 0, best = 0;
    long long total(TreeNode* n) {
        if (!n) return 0;
        long long s = n->val + total(n->left) + total(n->right);
        best = max(best, s * (T - s));
        return s;
    }
    int maxProduct(TreeNode* root) {
        T = total(root); best = 0;
        total(root);
        return best % 1000000007LL;
    }
};

Explanation

Cutting one edge splits the tree into a piece (the subtree hanging below that edge) and everything else. If the whole tree sums to T and the cut-off subtree sums to s, the two halves are s and T - s, so the product is simply s · (T - s).

That means we just need every subtree's sum. A single DFS computes total(n) = n.val + total(left) + total(right), and along the way we record each subtree sum in sums.

First we compute the grand total T. Then we look at each recorded subtree sum s and pick the one that maximizes s * (T - s) — this is largest when the two pieces are as balanced as possible.

The result is taken modulo 10⁹ + 7 because the product can grow very large.

Example: [1,2,3,4,5,6] has total T = 21. The best cut leaves sums 11 and 10, giving 11 · 10 = 110.

Time: O(n) Space: O(n)