Split a binary tree into two non-empty parts by removing one edge, and maximize the product of the sums of the two resulting subtrees.
Problem
You are given the root of a binary tree where each node contains an integer value.
Choose exactly one edge in the tree and remove it. This splits the tree into two non-empty connected components. Let the sum of node values in each component be and . Your task is to maximize the product
over all possible edge removals.
Return the maximum product modulo .
Notes
- The tree is binary, but the approach depends on subtree sums, not on BST properties.
- You must consider every possible edge whose removal splits the tree into two non-empty parts.
Input Format
- The input is the root of a binary tree.
- Each node has an integer value.
- The tree is connected and acyclic.
Output Format
- Return a single integer: the maximum product of the sums of the two subtrees formed by removing one edge, modulo .
Constraints
- The tree contains at least 2 nodes.
- Node values may be positive, zero, or negative unless the platform version specifies otherwise.
- The answer should be computed modulo .
- A linear-time traversal is expected for interview-quality solutions.
Example 1
Input
root = [1,2,3,4,5,6]
Output
110
Explanation
One optimal cut separates the subtree rooted at 2, whose sum is 11, from the rest of the tree whose sum is 10. The product is 110.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.