Maximum Product of Splitted Binary Tree Solution in Java

Navigate to Other Solutions
C++ Solution
Python Solution 

class Solution {
  public int maxProduct(TreeNode root) {
    final int kMod = 1_000_000_007;
    long ans = 0;
    List 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 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;
  }
}

Problem Description

Welcome to the world of binary trees, where every node is a potential split waiting to happen! The problem at hand is like trying to decide which pizza slice to eat first—do you go for the one with the most toppings or the one that’s just the right size? In the Maximum Product of Splitted Binary Tree, you are tasked with splitting a binary tree into two subtrees and maximizing the product of their sums.

Imagine you have a tree that represents your family tree, and you want to split it into two parts to see which side has the most “family wealth.” The catch? You can only split it at the nodes, and you want to maximize the product of the sums of the two resulting trees.

Approach Explanation

The code above employs a two-step approach. First, it calculates the total sum of the tree using a helper function treeSum, which recursively traverses the tree and collects the sums of all subtrees. Then, it iterates through these sums to find the maximum product of the split, ensuring to take the modulo 10^9 + 7 to avoid overflow.

Time and Space Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once to calculate the sums.
  • Space Complexity: O(N) in the worst case due to the storage of subtree sums in a list.

Real-World Example

Think of a company with a hierarchical structure represented as a binary tree. Each node represents a department, and the value at each node represents the revenue generated by that department. If the CEO (the root) wants to split the company into two divisions to maximize profits, they would need to find the optimal split point in the tree. This problem mirrors that scenario perfectly!

Similar Problems

If you enjoyed this problem, you might also like these: