Maximum Product of Splitted Binary Tree — Algorithm Visualization & Coding Challenge

🌳 1339. Maximum Product of Splitted Binary Tree

Difficulty: 🟡 Medium
Topics: Binary Tree, DFS, Tree DP

🧠 Problem Statement

You are given the root of a binary tree.
Your task is to split the tree into two subtrees by removing exactly one edge, such that:

🔹 The product of the sums of the two resulting subtrees is maximized

⚠️ Since the result can be very large:

• First, maximize the product
• Then return the result modulo \(10^9 + 7\)

✂️ How the Split Works

• Removing one edge divides the tree into two valid subtrees
• Each subtree has a sum of node values
• You must find the split that gives the maximum possible product

📌 Example 1

Input

root = [1,2,3,4,5,6]

Explanation

• Remove the highlighted edge
• Subtree sums = 11 and 10
• Product = 11 × 10 = 110

✅ Output

110

📌 Example 2

Input

root = [1,null,2,3,4,null,null,5,6]

Explanation

• Subtree sums = 15 and 6
• Product = 15 × 6 = 90

✅ Output

90

📏 Constraints

💡 Key Insight

• First compute the total sum of the tree
• For every possible subtree:
  • Let its sum be subSum
  • Other subtree sum = totalSum - subSum
  • Product = subSum × (totalSum - subSum)
• Track the maximum product
• Apply modulo after finding the maximum

🚀 This problem is a great example of using DFS + subtree sums efficiently!