Watch 10 video solutions for Maximum Product of Splitted Binary Tree, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by Fraz has 7,334 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 large, return it modulo 109 + 7.
Note that you need to maximize the answer before taking the mod and not after taking it.
Example 1:
Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)
Example 2:
Input: root = [1,null,2,3,4,null,null,5,6] Output: 90 Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)
Constraints:
[2, 5 * 104].1 <= Node.val <= 104Problem Overview: You are given the root of a binary tree. Remove exactly one edge so the tree splits into two subtrees. The goal is to maximize the product of the sums of the two resulting subtree values.
The key observation: if the total sum of the tree is S and a subtree has sum x, removing the edge above that subtree produces two parts with sums x and S - x. The product becomes x * (S - x). The problem reduces to computing every possible subtree sum and finding the split that maximizes this product.
Approach 1: Recursive Post-order Traversal (O(n) time, O(h) space)
This approach uses Depth-First Search with a post-order traversal of the binary tree. First compute the total sum of the entire tree. Then perform another DFS where each recursive call returns the sum of the current subtree. For each subtree sum x, compute the product x * (totalSum - x) and update the global maximum. Post-order works well because you need both left and right subtree sums before computing the current node’s sum. The recursion stack stores at most the tree height h, giving O(h) auxiliary space.
Approach 2: Iterative Post-order Traversal with Stack (O(n) time, O(n) space)
This version replaces recursion with an explicit stack while still performing post-order traversal on the tree. Nodes are pushed onto the stack and processed after their children, ensuring subtree sums are available before computing the parent sum. A hash map or dictionary stores intermediate subtree sums. Each node contributes exactly once to the total computation, keeping time complexity linear. This approach is useful in languages or environments where recursion depth could cause stack overflow or when you want tighter control over traversal order.
Both approaches rely on the same insight: compute subtree sums and evaluate the product for each possible edge removal. The final answer is returned modulo 1e9 + 7 as required by the problem.
Recommended for interviews: The recursive post-order DFS solution is what interviewers typically expect. It demonstrates strong understanding of subtree aggregation in trees and cleanly computes sums in a single traversal. Mentioning the iterative stack version shows deeper familiarity with traversal mechanics and recursion elimination.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Post-order Traversal | O(n) | O(h) | Best general solution. Clean implementation when recursion depth is manageable. |
| Iterative Post-order Traversal with Stack | O(n) | O(n) | Useful when avoiding recursion or handling very deep trees. |