## Code Avinya

Software Development Blogs

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

- 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.
- Next, we make a getSubtreeSum function, which is a helper function that calculates the sum of values in a subtree.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.

### About Us

Myself Bharath Choudhary, software developer at Oracle.

2021 NIT Warangal graduate.

### Categories

- About Companies (21)
- System Design (6)
- Uncategorized (36)

### Quick Contact

contact@codeavinya.com

Saturday – Sunday

10 AM – 5 PM

Follow Us :