1339. Maximum Product of Splitted Binary Tree

Hello, reader 👋🏽 ! Welcome to day 70 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1339. Maximum Product of Splitted Binary Tree.

🤔 Problem Statement

• 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.

• E.g.:

  • [1,2,3,4,5,6] => 110

  • [1,null,2,3,4,null,null,5,6] => 90

💬 Thought Process - Sum at every root

• The naive way of doing this would be to calculate the sum of every subtree and the rest of the tree for every root we separate.

• This could lead to worst case complexity of O(n^2). Plus, we would be doing repeated work by calculating the sum of the same subtrees again and again.

• Rather, if we know the total sum of the tree and the sum of subtree at every root, we can calculate the sum of the other split by splitTreeSum = totalSum - subtreeSum.

• Then, we can use the subtreeSum and splitTreeSum to calculate the product and then maximise this.

• So first, we will calculate the total sum from all the nodes in the tree.

• Then we will try to do a postorder traversal and calculate the subtree rooted at current node root. The left and right traversals give the sum of the left and right subtrees.

• We will assume that at every root, we are trying to separate this subtree from the rest of the tree.

• Since we know the sum of the left, right subtrees and the value at current node, the subtreeSum = sum(root.left) + sum(root.right) + root.val.

• Let the sum of the total tree be totalSum. The the sum of the rest of the tree excluding this subtreeSum will be totalSum - subtreeSum.

• Below is the illustration for the above process.

  

👩🏽‍💻 Solution - Maximum and minimum nodes

• Below is the code for the approach for calculating the difference of every path using the maximum and minimum nodes along that path.

/**
 * 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 maxProduct = 0;
    private long totalSum = 0;

    public int maxProduct(TreeNode root) {
        totalSum = getSum(root);
        getSum(root);

        return (int) (maxProduct % (1e9 + 7));
    }

    private long getSum(TreeNode root) {
        if(root == null) return 0;

        long leftSum = getSum(root.left);
        long rightSum = getSum(root.right);

        long sum = leftSum + rightSum + root.val;
        // remove this current node
        long product = (totalSum - sum) * sum;
        maxProduct = Math.max(product, maxProduct);
        return sum;
    }
}

Time Complexity: O(n)
  - n = number of nodes in the tree
Space Complexity: O(n)
  - n = number of nodes in the tree

• You can find the link to the GitHub repo for this question here: 1339. Maximum Product of Splitted Binary Tree.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!