🌳 Beginner-Friendly Guide 'Maximum Product of Splitted Binary Tree' – LeetCode 1339 (C++, Python, JavaScript)

#programming #cpp #javascript #python

Binary trees often feel intimidating because of their recursive nature. However, many tree problems can be solved by simply looking at how a single node relates to the rest of the structure. In this guide, we will learn how to "cut" an edge to maximize a mathematical product.

You're given:

The root of a binary tree where each node contains an integer value.

Your goal:

Split the tree into two separate subtrees by removing exactly one edge.
Calculate the sum of the nodes in each of the two resulting trees.
Maximize the product of these two sums and return the result modulo .

Intuition

The problem asks us to find two numbers (the sums of two subtrees) whose product is as large as possible. If we know the total sum of all nodes in the tree, let's call it , and we find the sum of any subtree, let's call it , then the sum of the remaining part of the tree must be .

To find the maximum product, we need to:

Calculate the Total Sum: We first traverse the entire tree to find the sum of every node. This gives us our constant .
Evaluate Every Possible Split: Every edge in the tree connects a parent to a subtree. If we "cut" that edge, the sum of one resulting tree is the sum of that subtree.
Calculate the Product: For every subtree sum we find, we calculate the product: .
Track the Maximum: We keep a running record of the largest product found during our traversal.

The key takeaway is that a Post-Order Traversal (Left, Right, Node) is perfect here. It allows a node to know the sum of its children before calculating its own total sum.

Code Blocks

C++

class Solution {
public:
    long long mod = 1e9 + 7;
    long long total = 0;
    long long ans = 0;

    long long subTreeSum(TreeNode* root) {
        if (root == nullptr) return 0;

        long long leftSum = subTreeSum(root->left);
        long long rightSum = subTreeSum(root->right);

        // Check product if we cut the edge to the left child
        ans = max(ans, (leftSum * (total - leftSum)));
        // Check product if we cut the edge to the right child
        ans = max(ans, (rightSum * (total - rightSum)));

        return leftSum + rightSum + root->val;
    }

    void calculateTotal(TreeNode* root) {
        if (root == nullptr) return;
        total += root->val;
        calculateTotal(root->left);
        calculateTotal(root->right);
    }

    int maxProduct(TreeNode* root) {
        calculateTotal(root);
        subTreeSum(root);
        return ans % mod;
    }
};

Python

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        self.total = 0
        self.ans = 0

        # First pass to find the total sum of all nodes
        def get_total(node):
            if not node:
                return
            self.total += node.val
            get_total(node.left)
            get_total(node.right)

        # Second pass to find subtree sums and calculate products
        def get_subtree_sum(node):
            if not node:
                return 0

            left_s = get_subtree_sum(node.left)
            right_s = get_subtree_sum(node.right)

            current_sum = left_s + right_s + node.val

            # Update max product: current_sum * (total - current_sum)
            # We don't take mod yet to ensure we find the true maximum
            self.ans = max(self.ans, current_sum * (self.total - current_sum))

            return current_sum

        get_total(root)
        get_subtree_sum(root)

        return self.ans % (10**9 + 7)

JavaScript

var maxProduct = function(root) {
    let total = 0;
    let ans = 0;

    // Helper to find the total sum of the tree
    const getTotal = (node) => {
        if (!node) return;
        total += node.val;
        getTotal(node.left);
        getTotal(node.right);
    };

    // Helper to find subtree sums and track maximum product
    const getSubtreeSum = (node) => {
        if (!node) return 0;

        const leftSum = getSubtreeSum(node.left);
        const rightSum = getSubtreeSum(node.right);

        const currentSum = leftSum + rightSum + node.val;

        // Calculate potential product
        const product = currentSum * (total - currentSum);
        if (product > ans) {
            ans = product;
        }

        return currentSum;
    };

    getTotal(root);
    getSubtreeSum(root);

    // Using BigInt for large number precision before modulo if necessary
    // but standard Number works for 5 * 10^4 nodes and 10^4 values
    return Number(BigInt(ans) % BigInt(1000000007));
};

Key Takeaways

Post-Order Traversal: This problem showcases how useful it is to process children before processing the parent. This allows us to "bubble up" sums from the leaves to the root.
Two-Pass Strategy: Sometimes it is easier to solve a problem by traversing the data structure twice: once to gather global information (total sum) and once to perform the specific logic (product calculation).
Precision and Modulo: Notice that we maximize the product before applying the modulo. Applying modulo early can lead to the wrong "maximum" because a larger number might result in a smaller remainder.

Final Thoughts

As a mentor, I often see students struggle with tree problems because they try to visualize every split at once. Instead, focus on the property of a single node: "If I know the sum of everything below me, I can determine the sum of the rest of the tree."

This logic is foundational in Network Routing Algorithms, where engineers must determine the best place to split traffic or identify "bottleneck" nodes. It is also highly relevant in Hierarchical Clustering within data science. Mastering these recursive patterns will make you a much more effective software engineer.

DEV Community