1339. Maximum Product of Splitted Binary Tree LeetCode Solution

In this guide, you will get 1339. Maximum Product of Splitted Binary Tree LeetCode Solution with the best time and space complexity. The solution to Maximum Product of Splitted Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Product of Splitted Binary Tree solution in C++
Maximum Product of Splitted Binary Tree solution in Java
Maximum Product of Splitted Binary Tree solution in Python
Additional Resources

1339. Maximum Product of Splitted Binary Tree LeetCode Solution image

Problem Statement of Maximum Product of Splitted Binary Tree

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:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1339. Maximum Product of Splitted Binary Tree LeetCode Solution in C++

class Solution {
 public:
  int maxProduct(TreeNode* root) {
    constexpr int kMod = 1'000'000'007;
    long ans = 0;
    vector<int> allSums;
    const long totalSum = treeSum(root, allSums);

    for (const long sum : allSums)
      ans = max(ans, sum * (totalSum - sum));

    return ans % kMod;
  }

 private:
  int treeSum(TreeNode* root, vector<int>& allSums) {
    if (root == nullptr)
      return 0;

    const int leftSum = treeSum(root->left, allSums);
    const int rightSum = treeSum(root->right, allSums);
    const int sum = root->val + leftSum + rightSum;
    allSums.push_back(sum);
    return sum;
  }
};
/* code provided by PROGIEZ */

1339. Maximum Product of Splitted Binary Tree LeetCode Solution in Java

class Solution {
  public int maxProduct(TreeNode root) {
    final int kMod = 1_000_000_007;
    long ans = 0;
    List<Integer> allSums = new ArrayList<>();
    final long totalSum = treeSum(root, allSums);

    for (final long sum : allSums)
      ans = Math.max(ans, sum * (totalSum - sum));

    return (int) (ans % kMod);
  }

  private int treeSum(TreeNode root, List<Integer> allSums) {
    if (root == null)
      return 0;

    final int leftSum = treeSum(root.left, allSums);
    final int rightSum = treeSum(root.right, allSums);
    final int sum = root.val + leftSum + rightSum;
    allSums.add(sum);
    return sum;
  }
}
// code provided by PROGIEZ