# Maximum Product of Splitted Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-product-of-splitted-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-splitted-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-product-of-splitted-binary-tree/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-product-of-splitted-binary-tree/image1.png) 

**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:**

* The number of nodes in the tree is in the range `[2, 5 * 104]`.
* `1 <= Node.val <= 104`

# Approaches
## Brute Force with Redundant Sum Calculation
This naive approach considers every possible split one by one. A split is made by removing an edge. For each potential split, it traverses the two resulting new trees to calculate their respective sums and then computes their product. It keeps track of the maximum product found across all possible splits.
**Time:** O(N^2), where N is the number of nodes. The `traverseAndCalculate` function visits N nodes. Inside it, `getSubtreeSum` is called, which may traverse up to N nodes in the worst case. This results in a quadratic time complexity. · **Space:** O(N), where N is the number of nodes. In the worst case of a skewed tree, the recursion stack for both the outer and inner traversals can go up to N levels deep.
**Pros:** Conceptually straightforward as it directly simulates checking every possible split.
**Cons:** Highly inefficient due to the nested traversal structure, leading to repeated calculations of subtree sums.; This approach will likely exceed the time limit for the given constraints.
### Explanation
The algorithm works by identifying every edge in the tree and simulating its removal. A more structured way to do this is to iterate through every node, consider the subtree rooted at that node as one part of the split, and calculate the product. This involves a main traversal to select split points and nested traversals to calculate sums, leading to poor performance.

```java
class Solution {
    long maxProduct = 0;
    long totalSum = 0;

    public int maxProduct(TreeNode root) {
        // Pre-calculate total sum to avoid one of the traversals inside the loop.
        totalSum = getSubtreeSum(root);
        // Traverse again to check every split.
        traverseAndCalculate(root, root);
        return (int) (maxProduct % 1000000007);
    }

    // Main traversal to iterate through each node as a potential split point.
    private void traverseAndCalculate(TreeNode node, TreeNode root) {
        if (node == null) {
            return;
        }

        // For each node, calculate its subtree sum (again).
        // This re-calculation is the source of inefficiency.
        long subtreeSum = getSubtreeSum(node);

        // We don't consider the case where the subtree is the whole tree,
        // as this corresponds to no split.
        if (node != root) {
            maxProduct = Math.max(maxProduct, subtreeSum * (totalSum - subtreeSum));
        }

        traverseAndCalculate(node.left, root);
        traverseAndCalculate(node.right, root);
    }

    // Helper to calculate sum of a subtree starting from 'node'.
    private long getSubtreeSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + getSubtreeSum(node.left) + getSubtreeSum(node.right);
    }
}
```
### Algorithm
1. First, perform a preliminary traversal (like DFS) to calculate the `totalSum` of all nodes in the tree. This helps in easily finding the sum of the second part of any split.
2. Traverse the tree again. For each node `n` in the tree (except the root), consider it as the root of a potential subtree to be split off.
3. To find the sum of the subtree rooted at `n`, perform a full traversal starting from `n`. Let's call this `subtreeSum`.
4. The sum of the other part of the tree is simply `totalSum - subtreeSum`.
5. Calculate the product: `product = subtreeSum * (totalSum - subtreeSum)`.
6. Keep a global `maxProduct` variable and update it if the current `product` is larger.
7. After iterating through all possible nodes `n` to form a split, the `maxProduct` will hold the maximum possible value. Return this value modulo 10^9 + 7.

## Optimal Two-Pass DFS
A highly efficient approach that avoids redundant computations by using two passes over the tree. The first pass calculates the total sum of all nodes. The second pass, a post-order traversal, calculates the sum of each subtree and simultaneously determines the maximum product without recalculating sums.
**Time:** O(N), where N is the number of nodes. The tree is traversed twice, and each traversal visits every node exactly once. The total time is O(N) + O(N) = O(N). · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, this becomes O(N).
**Pros:** Optimal time complexity, making it very efficient for large trees.; Efficiently reuses computed information (subtree sums) through the post-order traversal mechanism, avoiding redundant work.
**Cons:** Requires two separate passes over the tree, although this does not affect the overall asymptotic complexity.; Uses a member variable (`maxProduct`) to pass information up, which is a common pattern but can be less clean than pure functional approaches.
### Explanation
The key insight is that removing any edge partitions the tree into a specific subtree and "the rest of the tree". The sum of "the rest" can be found by subtracting the subtree's sum from the total sum of the original tree. We can find all possible subtree sums efficiently in a single post-order traversal. This avoids the O(N^2) complexity of the brute-force approach.

```java
class Solution {
    long maxProduct = 0;

    public int maxProduct(TreeNode root) {
        // Pass 1: Calculate the total sum of the tree.
        long totalSum = findTotalSum(root);
        
        // Pass 2: Use a post-order traversal to find each subtree's sum
        // and calculate the product against the remaining part of the tree.
        findMaxProduct(root, totalSum);
        
        return (int) (maxProduct % 1000000007);
    }

    // Helper for Pass 1: Simple DFS to sum all nodes.
    private long findTotalSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + findTotalSum(node.left) + findTotalSum(node.right);
    }

    // Helper for Pass 2: Post-order traversal that returns a subtree's sum
    // and updates the global maxProduct.
    private long findMaxProduct(TreeNode node, long totalSum) {
        if (node == null) {
            return 0;
        }
        
        // Post-order traversal: process children first.
        long leftSum = findMaxProduct(node.left, totalSum);
        long rightSum = findMaxProduct(node.right, totalSum);
        
        // Process current node.
        long subtreeSum = node.val + leftSum + rightSum;
        
        // Calculate product for the split defined by this subtree.
        // The split at the root (where subtreeSum == totalSum) gives a product of 0,
        // which is fine as it won't be the maximum.
        long product = subtreeSum * (totalSum - subtreeSum);
        maxProduct = Math.max(maxProduct, product);
        
        // Return this subtree's sum to the parent.
        return subtreeSum;
    }
}
```
### Algorithm
1. **Pass 1:** Traverse the entire tree once (using DFS or BFS) to compute the `totalSum` of all node values. It's crucial to use a `long` for the sum to prevent potential overflow, as the total sum can exceed the capacity of a 32-bit integer.
2. Initialize a `long` variable `maxProduct = 0` to store the maximum product found.
3. **Pass 2:** Perform a second, post-order DFS traversal. This traversal function will compute and return the sum of the subtree at the current node.
4. Inside the post-order traversal for a node `n`:
    a. Recursively find the sums of the left and right subtrees: `leftSum` and `rightSum`.
    b. Calculate the sum of the subtree rooted at `n`: `subtreeSum = n.val + leftSum + rightSum`.
    c. This `subtreeSum` represents the sum of one of the two trees if the edge connecting `n` to its parent is cut. The sum of the other tree is `totalSum - subtreeSum`.
    d. Calculate the product using 64-bit integers (`long`): `product = subtreeSum * (totalSum - subtreeSum)`.
    e. Update the global maximum: `maxProduct = Math.max(maxProduct, product)`.
    f. Return `subtreeSum` to its parent caller, allowing the sums to be built up from the leaves to the root.
5. After the second pass is complete, `maxProduct` will hold the maximum possible product. Return `maxProduct % (10^9 + 7)`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private long ans ; private long s ; public int maxProduct ( TreeNode root ) { final int mod = ( int ) 1 e9 + 7 ; s = sum ( root ); dfs ( root ); return ( int ) ( ans % mod ); } private long dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } long t = root . val + dfs ( root . left ) + dfs ( root . right ); if ( t < s ) { ans = Math . max ( ans , t * ( s - t )); } return t ; } private long sum ( TreeNode root ) { if ( root == null ) { return 0 ; } return root . val + sum ( root . left ) + sum ( root . right ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxProduct ( TreeNode * root ) { using ll = long long ; ll ans = 0 ; const int mod = 1e9 + 7 ; function < ll ( TreeNode * ) > sum = [ & ]( TreeNode * root ) -> ll { if ( ! root ) { return 0 ; } return root -> val + sum ( root -> left ) + sum ( root -> right ); }; ll s = sum ( root ); function < ll ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) -> ll { if ( ! root ) { return 0 ; } ll t = root -> val + dfs ( root -> left ) + dfs ( root -> right ); if ( t < s ) { ans = max ( ans , t * ( s - t )); } return t ; }; dfs ( root ); return ans % mod ; } };
```

### Python

```python
# 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 : Optional [ TreeNode ]) -> int : def sum ( root : Optional [ TreeNode ]) -> int : if root is None : return 0 return root . val + sum ( root . left ) + sum ( root . right ) def dfs ( root : Optional [ TreeNode ]) -> int : if root is None : return 0 t = root . val + dfs ( root . left ) + dfs ( root . right ) nonlocal ans , s if t < s : ans = max ( ans , t * ( s - t )) return t mod = 10 ** 9 + 7 s = sum ( root ) ans = 0 dfs ( root ) return ans % mod
```