Scale Engineer

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
TreeBinary 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 109 + 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 * 104].
  • 1 <= Node.val <= 104

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

  1. 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.
  2. 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.
  3. To find the sum of the subtree rooted at n, perform a full traversal starting from n. Let's call this subtreeSum.
  4. The sum of the other part of the tree is simply totalSum - subtreeSum.
  5. Calculate the product: product = subtreeSum * (totalSum - subtreeSum).
  6. Keep a global maxProduct variable and update it if the current product is larger.
  7. 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.

class Solution {    long maxProduct = 0;    long totalSum = 0;     public int maxProduct(TreeNode root) {        // Pre-calculate total sum to avoid one of the traversals inside the loop.        totalSum = getSubtreeSum(root);        // Traverse again to check every split.        traverseAndCalculate(root, root);        return (int) (maxProduct % 1000000007);    }     // Main traversal to iterate through each node as a potential split point.    private void traverseAndCalculate(TreeNode node, TreeNode root) {        if (node == null) {            return;        }         // For each node, calculate its subtree sum (again).        // This re-calculation is the source of inefficiency.        long subtreeSum = getSubtreeSum(node);         // We don't consider the case where the subtree is the whole tree,        // as this corresponds to no split.        if (node != root) {            maxProduct = Math.max(maxProduct, subtreeSum * (totalSum - subtreeSum));        }         traverseAndCalculate(node.left, root);        traverseAndCalculate(node.right, root);    }     // Helper to calculate sum of a subtree starting from 'node'.    private long getSubtreeSum(TreeNode node) {        if (node == null) {            return 0;        }        return node.val + getSubtreeSum(node.left) + getSubtreeSum(node.right);    }}

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.

Solutions

/** * 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 ); } }

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 →

Next problem