Maximum Product of Splitted Binary Tree

Med

#1244Time: O(N^2), where N is the number of nodes. The `traverseAndCalculate` function visits N nodes. Inside it, `getSubtreeSum` is called, which may traverse up to N nodes in the worst case. This results in a quadratic time complexity.Space: O(N), where N is the number of nodes. In the worst case of a skewed tree, the recursion stack for both the outer and inner traversals can go up to N levels deep.

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Prompt

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 that you need to maximize the answer before taking the mod and not after taking it.

Example 1:

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)

Example 2:

Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This naive approach considers every possible split one by one. A split is made by removing an edge. For each potential split, it traverses the two resulting new trees to calculate their respective sums and then computes their product. It keeps track of the maximum product found across all possible splits.

Algorithm

First, perform a preliminary traversal (like DFS) to calculate the totalSum of all nodes in the tree. This helps in easily finding the sum of the second part of any split.
Traverse the tree again. For each node n in the tree (except the root), consider it as the root of a potential subtree to be split off.
To find the sum of the subtree rooted at n, perform a full traversal starting from n. Let's call this subtreeSum.
The sum of the other part of the tree is simply totalSum - subtreeSum.
Calculate the product: product = subtreeSum * (totalSum - subtreeSum).
Keep a global maxProduct variable and update it if the current product is larger.
After iterating through all possible nodes n to form a split, the maxProduct will hold the maximum possible value. Return this value modulo 10^9 + 7.

Walkthrough

The algorithm works by identifying every edge in the tree and simulating its removal. A more structured way to do this is to iterate through every node, consider the subtree rooted at that node as one part of the split, and calculate the product. This involves a main traversal to select split points and nested traversals to calculate sums, leading to poor performance.

1class Solution {2    long maxProduct = 0;3    long totalSum = 0;4 5    public int maxProduct(TreeNode root) {6        // Pre-calculate total sum to avoid one of the traversals inside the loop.7        totalSum = getSubtreeSum(root);8        // Traverse again to check every split.9        traverseAndCalculate(root, root);10        return (int) (maxProduct % 1000000007);11    }12 13    // Main traversal to iterate through each node as a potential split point.14    private void traverseAndCalculate(TreeNode node, TreeNode root) {15        if (node == null) {16            return;17        }18 19        // For each node, calculate its subtree sum (again).20        // This re-calculation is the source of inefficiency.21        long subtreeSum = getSubtreeSum(node);22 23        // We don't consider the case where the subtree is the whole tree,24        // as this corresponds to no split.25        if (node != root) {26            maxProduct = Math.max(maxProduct, subtreeSum * (totalSum - subtreeSum));27        }28 29        traverseAndCalculate(node.left, root);30        traverseAndCalculate(node.right, root);31    }32 33    // Helper to calculate sum of a subtree starting from 'node'.34    private long getSubtreeSum(TreeNode node) {35        if (node == null) {36            return 0;37        }38        return node.val + getSubtreeSum(node.left) + getSubtreeSum(node.right);39    }40}

Complexity

Time

O(N^2), where N is the number of nodes. The `traverseAndCalculate` function visits N nodes. Inside it, `getSubtreeSum` is called, which may traverse up to N nodes in the worst case. This results in a quadratic time complexity.

Space

O(N), where N is the number of nodes. In the worst case of a skewed tree, the recursion stack for both the outer and inner traversals can go up to N levels deep.

Trade-offs

Pros

Conceptually straightforward as it directly simulates checking every possible split.

Cons

Highly inefficient due to the nested traversal structure, leading to repeated calculations of subtree sums.
This approach will likely exceed the time limit for the given constraints.

A highly efficient approach that avoids redundant computations by using two passes over the tree. The first pass calculates the total sum of all nodes. The second pass, a post-order traversal, calculates the sum of each subtree and simultaneously determines the maximum product without recalculating sums.

Algorithm

Pass 1: Traverse the entire tree once (using DFS or BFS) to compute the totalSum of all node values. It's crucial to use a long for the sum to prevent potential overflow, as the total sum can exceed the capacity of a 32-bit integer.
Initialize a long variable maxProduct = 0 to store the maximum product found.
Pass 2: Perform a second, post-order DFS traversal. This traversal function will compute and return the sum of the subtree at the current node.
Inside the post-order traversal for a node n: a. Recursively find the sums of the left and right subtrees: leftSum and rightSum. b. Calculate the sum of the subtree rooted at n: subtreeSum = n.val + leftSum + rightSum. c. This subtreeSum represents the sum of one of the two trees if the edge connecting n to its parent is cut. The sum of the other tree is totalSum - subtreeSum. d. Calculate the product using 64-bit integers (long): product = subtreeSum * (totalSum - subtreeSum). e. Update the global maximum: maxProduct = Math.max(maxProduct, product). f. Return subtreeSum to its parent caller, allowing the sums to be built up from the leaves to the root.
After the second pass is complete, maxProduct will hold the maximum possible product. Return maxProduct % (10^9 + 7).

Walkthrough

The key insight is that removing any edge partitions the tree into a specific subtree and "the rest of the tree". The sum of "the rest" can be found by subtracting the subtree's sum from the total sum of the original tree. We can find all possible subtree sums efficiently in a single post-order traversal. This avoids the O(N^2) complexity of the brute-force approach.

1class Solution {2    long maxProduct = 0;3 4    public int maxProduct(TreeNode root) {5        // Pass 1: Calculate the total sum of the tree.6        long totalSum = findTotalSum(root);7        8        // Pass 2: Use a post-order traversal to find each subtree's sum9        // and calculate the product against the remaining part of the tree.10        findMaxProduct(root, totalSum);11        12        return (int) (maxProduct % 1000000007);13    }14 15    // Helper for Pass 1: Simple DFS to sum all nodes.16    private long findTotalSum(TreeNode node) {17        if (node == null) {18            return 0;19        }20        return node.val + findTotalSum(node.left) + findTotalSum(node.right);21    }22 23    // Helper for Pass 2: Post-order traversal that returns a subtree's sum24    // and updates the global maxProduct.25    private long findMaxProduct(TreeNode node, long totalSum) {26        if (node == null) {27            return 0;28        }29        30        // Post-order traversal: process children first.31        long leftSum = findMaxProduct(node.left, totalSum);32        long rightSum = findMaxProduct(node.right, totalSum);33        34        // Process current node.35        long subtreeSum = node.val + leftSum + rightSum;36        37        // Calculate product for the split defined by this subtree.38        // The split at the root (where subtreeSum == totalSum) gives a product of 0,39        // which is fine as it won't be the maximum.40        long product = subtreeSum * (totalSum - subtreeSum);41        maxProduct = Math.max(maxProduct, product);42        43        // Return this subtree's sum to the parent.44        return subtreeSum;45    }46}

Complexity

Time

O(N), where N is the number of nodes. The tree is traversed twice, and each traversal visits every node exactly once. The total time is O(N) + O(N) = O(N).

Space

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, this becomes O(N).

Trade-offs

Pros

Optimal time complexity, making it very efficient for large trees.
Efficiently reuses computed information (subtree sums) through the post-order traversal mechanism, avoiding redundant work.

Cons

Requires two separate passes over the tree, although this does not affect the overall asymptotic complexity.
Uses a member variable (maxProduct) to pass information up, which is a common pattern but can be less clean than pure functional approaches.

Solutions

Solution

1/** * 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 { private long ans ; private long s ; public int maxProduct ( TreeNode root ) { final int mod = ( int ) 1 e9 + 7 ; s = sum ( root ); dfs ( root ); return ( int ) ( ans % mod ); } private long dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } long t = root . val + dfs ( root . left ) + dfs ( root . right ); if ( t < s ) { ans = Math . max ( ans , t * ( s - t )); } return t ; } private long sum ( TreeNode root ) { if ( root == null ) { return 0 ; } return root . val + sum ( root . left ) + sum ( root . right ); } }

1/** * 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 ) { using ll = long long ; ll ans = 0 ; const int mod = 1e9 + 7 ; function < ll ( TreeNode * ) > sum = [ & ]( TreeNode * root ) -> ll { if ( ! root ) { return 0 ; } return root -> val + sum ( root -> left ) + sum ( root -> right ); }; ll s = sum ( root ); function < ll ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) -> ll { if ( ! root ) { return 0 ; } ll t = root -> val + dfs ( root -> left ) + dfs ( root -> right ); if ( t < s ) { ans = max ( ans , t * ( s - t )); } return t ; }; dfs ( root ); return ans % mod ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def maxProduct ( self , root : Optional [ TreeNode ]) -> int : def sum ( root : Optional [ TreeNode ]) -> int : if root is None : return 0 return root . val + sum ( root . left ) + sum ( root . right ) def dfs ( root : Optional [ TreeNode ]) -> int : if root is None : return 0 t = root . val + dfs ( root . left ) + dfs ( root . right ) nonlocal ans , s if t < s : ans = max ( ans , t * ( s - t )) return t mod = 10 ** 9 + 7 s = sum ( root ) ans = 0 dfs ( root ) return ans % mod

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem