hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Maximum Product of Splitted Binary Tree


  • Approach:

    1. The first step is to traverse the binary tree, to sum up, all the node values.

    2. Then traverse the tree again and subtract the sum of any sub-tree sum (left sub-tree sum + right sub-tree sum + current node's sum).

    3. So, left_sum = total - current sub-tree sum.

    4. Now multiply left_sum with the current sub-tree sum.

    5. Take the maximum among the multiplied values.

    6. Return the maximum modulo 109 + 7.


  • Time and Space Complexity:

    • Time Complexity: O(N)

    • Space Complexity: O(1) + Auxilary Recursive Stack

Code [C++]

/**

* 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:

const int MOD = 1e9 + 7;

long long maxVal = 0, total;

bool type = 0;


long long solve(TreeNode * root){

if(!root) return 0;

long long left = solve(root->left);

long long right = solve(root->right);

if(type){

maxVal = max(maxVal, left * (total - left));

maxVal = max(maxVal, right * (total - right));

long long newSum =(left + right + root->val);

maxVal = max(maxVal, newSum * (total - newSum));

}

return (left + right + root->val);

}


int maxProduct(TreeNode* root) {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

total = solve(root); type = true;

solve(root);

return maxVal % MOD;

}

};