LeetCode 1339 Explained: Maximum Product of Splitted Binary Tree

Problem Overview

You are given the root of a binary tree.
You are allowed to split the tree into two subtrees by removing exactly one edge.

The goal is to maximize the product of the sums of the two resulting subtrees.

Since the result can be large, return the answer modulo 10⁹ + 7.

---

Key Insight

When you remove one edge in a tree:

• One subtree gets the sum of all nodes below that edge
• The other subtree gets the sum of all remaining nodes

If:

• totalSum = sum of all nodes in the tree
• subtreeSum = sum of one subtree after cutting an edge

Then the product is:

subtreeSum × (totalSum − subtreeSum)

So the problem reduces to:

Find the subtree whose sum maximizes this product

---

Strategy

Step 1: Compute Total Tree Sum

We first traverse the entire tree to calculate the total sum of all nodes.

This is needed to compute the complementary subtree sum after each split.

---

Step 2: DFS to Try All Possible Splits

Perform a postorder DFS:

• For every node, compute the sum of its subtree
• Consider the product formed by cutting the edge above this subtree
• Track the maximum product seen so far

Postorder is important because:

• We must know the sum of left and right subtrees before computing the current subtree sum

---

Why This Works

Every valid split corresponds to cutting one edge.
Cutting an edge means choosing any subtree root except the original root.

By computing subtree sums at every node, we effectively evaluate all possible splits.

---

Algorithm

1. DFS to compute totalSum
2. DFS again to compute subtree sums and track max product
3. Return result modulo 10^9 + 7

---

Implementation (Python)

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        MOD = 10**9 + 7
        self.max_product = 0

        # Step 1: Compute total sum
        def total_sum(node):
            if not node:
                return 0
            return node.val + total_sum(node.left) + total_sum(node.right)

        total = total_sum(root)

        # Step 2: Postorder DFS to compute subtree sums
        def dfs(node):
            if not node:
                return 0

            left_sum = dfs(node.left)
            right_sum = dfs(node.right)
            subtree_sum = node.val + left_sum + right_sum

            # Try splitting here
            product = subtree_sum * (total - subtree_sum)
            self.max_product = max(self.max_product, product)

            return subtree_sum

        dfs(root)
        return self.max_product % MOD

---

Complexity Analysis

Metric	Value
Time Complexity	O(n)
Space Complexity	O(h) (recursion stack)

Where:

• n = number of nodes
• h = height of the tree

---

Example Walkthrough

Tree:

      1
     / \
    2   3

• Total sum = 6
• Possible splits:
  • Cut edge above 2: 2 × 4 = 8
  • Cut edge above 3: 3 × 3 = 9

✅ Maximum product = 9

---

Common Pitfalls

❌ Trying to split only at leaf nodes
❌ Forgetting modulo at the end
❌ Using preorder instead of postorder
❌ Recomputing subtree sums repeatedly (O(n²))

---

Key Takeaways

• Tree splitting problems often reduce to subtree sum analysis
• Postorder traversal is ideal for bottom-up calculations
• Every subtree represents a potential split
• Separating total sum computation simplifies the logic

---

Final Thought

This problem is a classic example of turning a structural tree operation into a numerical optimization problem using DFS.

Once you see that every edge corresponds to a subtree sum, the solution becomes elegant and efficient.

Happy coding 🚀