Maximum Product of Splitted Binary Tree - Practice Coding Problems

Maximum Product of Splitted Binary Tree - Problem

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 10⁹ + 7.

Note: You need to maximize the answer before taking the mod and not after taking it.

Input & Output

Example 1 — Basic Tree

$ Input: root = [1,2,3,4,5,6]

› Output: 110

💡 Note: Remove edge above node 2. Left subtree sum = 2+4+5 = 11, right subtree sum = 1+3+6 = 10. Product = 11 × 10 = 110

Example 2 — Simple Tree

$ Input: root = [1,null,2,3,4,null,null,5,6]

› Output: 90

💡 Note: Remove edge above node 3. Left subtree sum = 3+5 = 8, remaining sum = 1+2+4+6 = 13. But removing above node 4 gives: subtree = 4+6 = 10, remaining = 9. Product = 10 × 9 = 90

Example 3 — Single Split

$ Input: root = [2,3,9,10,7,8,6,5,4,11,1]

› Output: 1025

💡 Note: Find the optimal cut that maximizes the product of the two resulting subtree sums

Constraints

The number of nodes in the tree is in the range [2, 5 × 10⁴]
1 ≤ Node.val ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with node values [1,2,3,4,5,6]

Find Best Cut

Try removing each edge to split into two subtrees

Maximum Product

Cut above node 2 gives product 110

Key Takeaway

🎯 Key Insight: Use DFS to efficiently calculate subtree sums and find the optimal cut point

Asked in

a Amazon 35 G Google 28 M Microsoft 22 f Facebook 18

The key insight is to use DFS to calculate subtree sums and find the cut that maximizes the product of two resulting subtrees. Best approach uses two-pass DFS: first to get total sum, second to check all possible cuts. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS - Two Pass	O(n)	O(h)	Calculate subtree sums once using DFS, then find maximum product
Brute Force - Try All Edges	O(n²)	O(h)	For each edge, calculate subtree sums and their product

Optimized DFS - Two Pass — Algorithm Steps

Step 1: First DFS to calculate total sum of the tree
Step 2: Second DFS to calculate subtree sums bottom-up
Step 3: For each subtree, check product with remaining portion
Step 4: Return maximum product found modulo 10^9 + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

First Pass

Calculate total sum = 21

Second Pass

For each subtree, compute product with remaining

Track Maximum

Keep track of maximum product found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

long long totalSum = 0;
long long maxProduct = 0;
const int MOD = 1000000007;

long long calculateTotal(struct TreeNode* node) {
    if (!node) return 0;
    return node->val + calculateTotal(node->left) + calculateTotal(node->right);
}

long long dfs(struct TreeNode* node, struct TreeNode* root) {
    if (!node) return 0;
    
    long long leftSum = dfs(node->left, root);
    long long rightSum = dfs(node->right, root);
    long long currentSum = node->val + leftSum + rightSum;
    
    if (node != root) {
        long long remainingSum = totalSum - currentSum;
        long long product = currentSum * remainingSum;
        if (product > maxProduct) {
            maxProduct = product;
        }
    }
    
    return currentSum;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    totalSum = calculateTotal(root);
    maxProduct = 0;
    dfs(root, root);
    return maxProduct % MOD;
}

int main() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two DFS traversals, each visiting every node exactly once

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

52.0K Views

Medium-High Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS - Two Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler