Maximum Product of Splitted Binary Tree

We have solved many questions, but “Find Maximum Product of Splitted Binary Tree” is one of the toughest questions we have seen.

Question:

So, in this problem, we have given the root of a binary tree, and we have to split the binary tree into two subtrees by removing one edge. So, the product of the sums of the subtrees node should be maximized.

Code:

#include <iostream>
#include <unordered_map>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Helper function to calculate the sum of values in a subtree
int getSubtreeSum(TreeNode* node, unordered_map<TreeNode*, int>& subtreeSum) {
    if (node == NULL)
        return 0;
    
    int sum = node->val + getSubtreeSum(node->left, subtreeSum) + getSubtreeSum(node->right, subtreeSum);
    subtreeSum[node] = sum; // Storing the subtree sum for future use
    return sum;
}

// Recursive function to find the maximum product of splitted binary tree
long long int findMaxProduct(TreeNode* root, unordered_map<TreeNode*, int>& subtreeSum, long long int& maxProduct) {
    if (root == NULL)
        return 0;
    
    int leftSum = findMaxProduct(root->left, subtreeSum, maxProduct);
    int rightSum = findMaxProduct(root->right, subtreeSum, maxProduct);
    
    int totalSum = subtreeSum[root]; // Total sum of values in the current subtree
    int subtreeProduct = leftSum * (totalSum - leftSum); // Product of the sums of left and right subtrees
    
    maxProduct = max(maxProduct, (long long int)subtreeProduct); // Updating the maximum product if needed
    
    return totalSum;
}

// Function to find the maximum product of a splitted binary tree
int maxProduct(TreeNode* root) {
    unordered_map<TreeNode*, int> subtreeSum; // Map to store subtree sums
    
    // Calculating the sum of values in each subtree
    getSubtreeSum(root, subtreeSum);
    
    long long int maxProduct = 0;
    
    // Finding the maximum product of splitted binary tree
    findMaxProduct(root, subtreeSum, maxProduct);
    
    return maxProduct % int(1e9 + 7); // Returning the maximum product modulo 10^9 + 7
}

int main() {
    // Creating a binary tree manually
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    
    // Calling the function to find the maximum product of the splitted binary tree
    int result = maxProduct(root);
    
    cout << "Maximum product of splitted binary tree: " << result << endl;
    
    return 0;
}

Code Explanation:

To solve this problem, we have to find the maximum product by removing one edge from the tree. And here our goal is to find the maximum product of the sums of the values in these two subtrees.

1. First, we define a TreeNode struct to represent the nodes of the binary tree. Each node has a value, a left child, and a right child.
2. Next, we make a getSubtreeSum function, which is a helper function that calculates the sum of values in a subtree.
3. Here, we use a recursive approach to calculate the sum of values in the left and right subtrees and add the current node’s value to the sum. It also stores the subtree sum in the subtreeSum map for future use.
4. The findMaxProduct function is the main recursive function that will find the maximum product of a split binary tree. So, it takes the current node, the subtreeSum map, and a reference to maxProduct as parameters.
5. The above function will recursively calculate the sums of the values in the left and right subtrees and then calculates the product of these sums. After that, it updates the maxProduct if the calculated product is greater. And if not, then the sum will remain the same.
6. After this, we will make a maxProduct function. This function creates an unordered_map called subtreeSum to store the subtree sums. It calls the getSubtreeSum function to calculate the subtree sums and then initializes the maxProduct to 0.
7. It calls the findMaxProduct function to find the maximum product of the split binary tree. The maxProduct reference is passed to update the value of the maximum product.
8. In the main function, a binary tree is manually created by constructing the nodes and connecting them. The maxProduct function is called with the root of the binary tree, and the result is printed.
9. After that, the code calculates the maximum product of a split binary tree by utilizing recursive traversal and dynamic programming techniques.

Time Complexity:

The time complexity of the above code is O(N), where N is the number of nodes available in the binary tree. This is because we traverse each node in the tree once to calculate the subtree sums and find the maximum product.

Space Complexity:

The space complexity of the above code is also O(N) because we use an unordered map to store the subtree sums for each node in the tree.