Maximum Product of Splitted Binary Tree — Problem & Solution
Maximum Product of Splitted Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Product of Splitted Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, remove exactly one edge so that the tree falls apart into two subtrees, and make the product of the two subtrees' value sums as large as possible.
Return that largest product modulo 10^9 + 7. Note that you must maximise the product itself and only then take it modulo 10^9 + 7 — not maximise the remainder.
Example 1
Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Cutting the edge above 2 gives parts summing to 11 (2 + 4 + 5) and 10 (1 + 3 + 6); 11 × 10 = 110 is the largest product.
Example 2
Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
Explanation: Cutting above 4 splits the total 21 into 15 (4 + 5 + 6) and 6: 15 × 6 = 90.
Example 3
Input: root = [2,3]
Output: 6
Explanation: There is one edge: 2 × 3 = 6.
Constraints
2 <= number of nodes <= 5 · 10^41 <= Node.val <= 10^4
Hints for Maximum Product of Splitted Binary Tree
Hint 1
Cutting the edge above a node separates exactly that node's subtree from the rest.
Hint 2
If the whole tree sums to
Tand the subtree tos, the product iss · (T - s). So you needTand every subtree sum.Hint 3
Two walks: one for
T, then a post-order walk that computes each subtree sum and tracks the best product. The product can exceed 32 bits — use 64-bit arithmetic and reduce modulo only at the end.
How to solve Maximum Product of Splitted Binary Tree
Every cut separates one subtree from the rest, so the candidates are s · (T - s) for every subtree sum s. Compute the total first, then all subtree sums in one post-order walk.
Approach
- Compute
T, the sum of all node values. - Walk the tree in post-order; for each node compute its subtree sum
s = val + left sum + right sum. - Update the best with
s · (T - s)in 64-bit arithmetic. - Return
best mod (10^9 + 7).
Why it works
Removing the edge between a node and its parent leaves that node's subtree (sum s) and everything else (sum T - s); every edge is above exactly one non-root node, so every split is examined. The root's own sum gives the product 0 and never wins.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Taking the modulo before comparing products picks the wrong split.
Tcan reach 5 · 10^8, so the product reaches about 6 · 10^16 — overflow in 32-bit arithmetic, and past exact integers in a JavaScript double: there, choose the split whosesis closest toT / 2(the product only grows assnears half) and multiply once modulo the prime.
Reference solution
Python
from typing import Optional
def maxProduct(root: Optional[TreeNode]) -> int:
sums = []
def walk(node):
if node is None:
return 0
s = node.val + walk(node.left) + walk(node.right)
sums.append(s)
return s
total = walk(root)
best = max(s * (total - s) for s in sums)
return best % 1000000007Java
public static int maxProduct(TreeNode root) {
long total = sumTree(root);
long[] best = {0};
splitWalk(root, total, best);
return (int) (best[0] % 1000000007L);
}
static long sumTree(TreeNode node) {
return node == null ? 0 : node.val + sumTree(node.left) + sumTree(node.right);
}
static long splitWalk(TreeNode node, long total, long[] best) {
if (node == null) return 0;
long s = node.val + splitWalk(node.left, total, best) + splitWalk(node.right, total, best);
best[0] = Math.max(best[0], s * (total - s));
return s;
}C++
long long sumTree(TreeNode* node);
long long splitWalk(TreeNode* node, long long total, long long& best);
int maxProduct(TreeNode* root) {
long long total = sumTree(root), best = 0;
splitWalk(root, total, best);
return (int) (best % 1000000007LL);
}
long long sumTree(TreeNode* node) {
return node ? node->val + sumTree(node->left) + sumTree(node->right) : 0;
}
long long splitWalk(TreeNode* node, long long total, long long& best) {
if (!node) return 0;
long long s = node->val + splitWalk(node->left, total, best) + splitWalk(node->right, total, best);
best = max(best, s * (total - s));
return s;
}JavaScript
var maxProduct = function(root) {
var total = sumTree(root);
var state = { total: total, best: 0 };
splitWalk(root, state);
return mulMod(state.best, total - state.best, 1000000007);
};
var sumTree = function(node) {
return node === null ? 0 : node.val + sumTree(node.left) + sumTree(node.right);
};
// Keeps the subtree sum closest to total / 2: s * (total - s) grows as s nears half.
var splitWalk = function(node, state) {
if (node === null) return 0;
var s = node.val + splitWalk(node.left, state) + splitWalk(node.right, state);
if (Math.abs(state.total - 2 * s) < Math.abs(state.total - 2 * state.best)) state.best = s;
return s;
};
var mulMod = function(a, b, m) {
a %= m;
b %= m;
var hi = Math.floor(b / 65536), lo = b % 65536;
return ((a * hi) % m * 65536 + a * lo) % m;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals