Solution For 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.
Example:
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)
Solution:
First we need to find the sum of the entire binary tree.
Then we need to do a post-order traversal of the binary tree and for each node we need to find the sum of the subtree rooted at that node.
Then we can calculate the maximum product of the sums of the two subtrees by traversing the binary tree again. For each node, we can calculate the product of the sum of its left subtree and the sum of its right subtree and update the maximum product seen so far.
Finally, we return the maximum product modulo 109 + 7.
Here is the Python implementation of the solution:
class Solution:
def maxProduct(self, root: Optional[TreeNode]) -> int:
self.total_sum = 0
# Find the sum of the entire binary tree
def find_sum(root):
if not root:
return 0
left_sum = find_sum(root.left)
right_sum = find_sum(root.right)
self.total_sum += root.val + left_sum + right_sum
return root.val + left_sum + right_sum
# Find the sum of the subtree rooted at each node
def find_subtree_sum(root):
if not root:
return 0
left_sum = find_subtree_sum(root.left)
right_sum = find_subtree_sum(root.right)
root.subtree_sum = root.val + left_sum + right_sum
return root.subtree_sum
find_sum(root)
find_subtree_sum(root)
max_product = 0
# Calculate the maximum product of the sums of the subtrees
def find_max_product(root):
nonlocal max_product
if not root:
return 0
left_sum = find_max_product(root.left)
right_sum = find_max_product(root.right)
product = left_sum * (self.total_sum - left_sum) if left_sum else 0
product = max(product, right_sum * (self.total_sum - right_sum) if right_sum else 0)
product = max(product, max_product)
return root.subtree_sum
find_max_product(root)
return max_product % (10**9 + 7)
Step by Step Implementation For Maximum Product Of Splitted Binary Tree
/**
* 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 {
// maxProduct will keep track of the maximum product seen so far
// sum will keep track of the sum of all node values seen so far
long maxProduct = 0, sum = 0;
public int maxProduct(TreeNode root) {
// base case: if the tree is empty, return 0
if (root == null) {
return 0;
}
// get the sum of all node values in the tree
getSum(root);
// get the maximum product by starting from the root
getMaxProduct(root);
// return the maximum product modulo 10^9 + 7
return (int) (maxProduct % 1000000007);
}
// getSum will compute the sum of all node values in the tree
public void getSum(TreeNode root) {
// base case: if the tree is empty, return
if (root == null) {
return;
}
// add the current node's value to the sum
sum += root.val;
// recurse on the left and right subtrees
getSum(root.left);
getSum(root.right);
}
// getMaxProduct will compute the maximum product seen so far
// by starting from the given node
public void getMaxProduct(TreeNode root) {
// base case: if the tree is empty, return
if (root == null) {
return;
}
// compute the product of the current node's value and the sum of all other node values
long currProduct = root.val * (sum - root.val);
// update the maximum product seen so far, if necessary
maxProduct = Math.max(maxProduct, currProduct);
// recurse on the left and right subtrees
getMaxProduct(root.left);
getMaxProduct(root.right);
}
}# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxProduct(self, root: TreeNode) -> int:
# keep track of the sum of all values in the tree
# as we traverse the tree, we can compute the product
# of the left and right subtrees
# return the maximum product
self.total = 0
self.max_product = 0
def helper(node):
if not node:
return 0
# compute the sum of values in the left and right subtrees
left_sum = helper(node.left)
right_sum = helper(node.right)
# update the total sum of values in the tree
self.total += node.val
# compute the product of the left and right subtrees
product = left_sum * right_sum
# update the maximum product
self.max_product = max(self.max_product, product)
# return the sum of values in the current subtree
return self.total - (left_sum + right_sum) + node.val
helper(root)
return self.max_product % (10**9 + 7)/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxProduct = function(root) {
// edge case
if (!root) return 0;
// get the sum of all nodes
const sum = getSum(root);
// get the max product
return getMaxProduct(root, sum);
};
// get the sum of all nodes
const getSum = root => {
// base case
if (!root) return 0;
// recursively get the sum of left and right subtrees
return root.val + getSum(root.left) + getSum(root.right);
};
// get the max product
const getMaxProduct = (root, sum) => {
// base case
if (!root) return 0;
// get the sum of left and right subtrees
const leftSum = getSum(root.left);
const rightSum = getSum(root.right);
// return the max of left and right products
// or the current node's product
return Math.max(
leftSum * (sum - leftSum),
rightSum * (sum - rightSum),
getMaxProduct(root.left, sum),
getMaxProduct(root.right, sum)
);
};/**
* 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) {
int sum = getSum(root);
int maxProd = 0;
getMaxProd(root, sum, maxProd);
return maxProd % 1000000007;
}
int getSum(TreeNode* root) {
if (!root) return 0;
return root->val + getSum(root->left) + getSum(root->right);
}
void getMaxProd(TreeNode* root, int sum, int& maxProd) {
if (!root) return;
int currProd = (sum - root->val) * root->val;
maxProd = max(maxProd, currProd);
getMaxProd(root->left, sum, maxProd);
getMaxProd(root->right, sum, maxProd);
}
};/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public int MaxProduct(TreeNode root) {
// edge case
if (root == null) {
return 0;
}
// get sum of all nodes
int sum = GetSum(root);
// get max product by recursively splitting tree at each node
return GetMaxProduct(root, sum);
}
private int GetSum(TreeNode node) {
if (node == null) {
return 0;
}
return node.val + GetSum(node.left) + GetSum(node.right);
}
private int GetMaxProduct(TreeNode node, int sum) {
if (node == null) {
return 0;
}
// calculate product of current node being root of split tree
int product = (sum - node.val) * node.val;
// compare to max product of left and right subtrees
product = Math.Max(product, GetMaxProduct(node.left, sum));
product = Math.Max(product, GetMaxProduct(node.right, sum));
return product;
}
}