Problem Breakdown
We are given a binary tree where every node has a positive integer value. The goal is to remove exactly one edge from this tree to partition it into two separate subtrees. We want to maximize the product of the sum of values in these two new trees.
Inputs: Root of a non-empty binary tree (at least 2 nodes). Outputs: Maximum possible product modulo .
Constraints & Edge Cases:
- Node Values: Positive integers (), so sums are strictly increasing with depth. No negative values to complicate sum logic.
- Tree Size: At least 2 nodes ensures at least one edge exists to cut. A tree of size 2 has exactly one valid split (the root and the leaf).
- Overflow: The product can exceed -bit integer limits, but Python handles arbitrary precision integers automatically. We only apply modulo for the final return value or intermediate storage if we strictly needed memory optimization (not required here).
Intuition
A brute-force approach would be to iterate through every possible edge in the tree ( edges), cut it, and calculate the sum of both resulting components. Calculating sums naively for each cut takes time per cut, leading to an overall complexity of . Given constraints up to 50,000 nodes, this is too slow (, which might TLE).
Key Insight:
If we know the total sum of all nodes in the original tree (total_sum), removing an edge that separates a subtree with sum x automatically leaves the rest of the tree with sum total_sum - x. The product becomes .
Since this relationship holds for any valid cut, we simply need to find all possible values of x achievable by cutting any edge. We can do this efficiently using a Depth-First Search (DFS).
- Pass 1: Calculate the total sum of the entire tree (
total_sum). This is . - Pass 2: Traverse the tree again to identify every subtree that could be formed by cutting an edge above it. For each node, its children represent potential cuts. If a child returns a subtree sum
s, we calculate products * (total_sum - s)and update our maximum found so far. This is also .
Total Time Complexity: . Space Complexity: for recursion stack, where H is tree height ().
Approach
- Define a helper function
dfsthat returns the sum of values in the subtree rooted at the current node. - First, call this DFS to compute and store the total_sum of the entire binary tree.
- Initialize a global variable (or closure)
max_productto track the highest product found. - Perform a second traversal (DFS).
- For every node visited, recursively get sums from left and right children.
- The sum returned by a child represents one component of our split if we cut that edge. Let this be
subtree_sum. - Calculate the product:
current_product = subtree_sum * (total_sum - subtree_sum). - Update
max_productwithcurrent_product.
- Return
max_product % (10^9 + 7)at the end.
Complexity Analysis
- Time: , where N is the number of nodes. We traverse the tree twice: once to find total sum and once to check cuts. Each node is visited a constant number of times.
- Space: for recursion stack space in DFS, where H is the height of the tree. In worst case (skewed tree), this degrades to .
Solution
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxProduct(self, root: 'TreeNode') -> int:
MOD = 10**9 + 7
# Helper to calculate total sum of the tree (Pass 1)
def get_total_sum(node):
if not node:
return 0
left_sum = get_total_sum(node.left)
right_sum = get_total_sum(node.right)
return node.val + left_sum + right_sum
# Calculate total sum of the entire tree
total_sum = get_total_sum(root)
max_product = 0
# Helper to traverse and find cuts (Pass 2)
def dfs_split(node):
nonlocal max_product
if not node:
return 0
left_subtree_sum = dfs_split(node.left)
right_subtree_sum = dfs_split(node.right)
current_node_val = node.val
# The sum of the subtree rooted at this node (excluding parent edge cut logic yet?)
# Actually, we need to check cuts *above* children.
# When returning from a child call in recursion:
# 1. If left exists, cutting above it gives component 'left_subtree_sum' and rest 'total - that'.
if node.left:
product = left_subtree_sum * (total_sum - left_subtree_sum)
max_product = max(max_product, product)
if node.right:
product = right_subtree_sum * (total_sum - right_subtree_sum)
max_product = max(max_product, product)
# Return sum of current subtree for parent to use in its own cut calculation?
# Wait, the logic above checks cuts at children. What about cutting below this node's left child?
# That was handled when we were inside 'node.left'.
# We just need to return the total sum of THIS subtree up to here so parents can calculate their sums correctly for *their* cut calculations later (though strictly not needed if we only care about children cuts).
# However, standard pattern: Return current node's full subtree sum.
return left_subtree_sum + right_subtree_sum + current_node_val
dfs_split(root)
return max_product % MOD
Edge Cases Handled
- Minimum Nodes (2): The code naturally handles trees with 2 nodes where only one edge exists to cut.
dfs_splitwill process the leaf, calculate product based on total sum of both leaves + root logic correctly. - Large Values: Python’s arbitrary precision integers handle products exceeding without overflow before applying modulo at return.
- Skewed Trees (Recursion Depth): The recursion depth is proportional to tree height (). While this risks stack overflow in languages with fixed stacks, it fits within standard limits for 50k nodes on typical LeetCode environments unless the test case specifically targets Python’s default limit (which can be increased or handled iteratively if needed, but recursive DFS is idiomatic here).
- Single Edge Removal: The problem guarantees at least one edge exists. We iterate over all valid edges implicitly via child returns in
dfs_split.