hardTreesPure DSA~30 min
Maximum Product from Splitting a Tree
Cutting one edge of a weighted tree splits it into two components. To partition a workload tree into two balanced halves, maximize the product of the two component sums.
Problem
Given the root of a binary tree where each node has an integer value, remove exactly one edge to split the tree into two subtrees, maximizing the product of the sums of the two resulting subtrees. Return that maximum product modulo 1e9 + 7.
Input
The root of a binary tree (given as a level-order array in examples).
Output
An integer: the maximum product of the two subtree sums, modulo 1e9 + 7.
Constraints
- 2 <= n <= 50000
- 1 <= Node.val <= 10000
Examples
Example 1
Input
root = [1,2,3,4,5,6]
Output
110
Cutting an edge to isolate a subtree summing to 11 leaves 10; product 110.
Example 2
Input
root = [1,null,2,3,4,null,null,5,6]
Output
90
The best edge cut yields a product of 90.