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

Source: Dev.to

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.

---

Problem Statement

You are given:

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

Your goal:

1. Split the tree into two separate subtrees by removing exactly one edge.
2. Calculate the sum of the nodes in each of the two resulting trees.
3. Maximize the product of these two sums and return the result modulo (10^9 + 7).

---

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, call it (S), and we find the sum of any subtree, call it (x), then the sum of the remaining part of the tree must be (S - x).

To obtain the maximum product we need to:

1. Calculate the total sum – traverse the entire tree once to compute (S).
2. Evaluate every possible split – each edge connects a parent to a subtree. Cutting that edge yields a subtree sum (x).
3. Calculate the product – for each subtree sum compute (x \times (S - x)).
4. Track the maximum – keep the largest product seen during the traversal.

A post‑order traversal (left, right, node) is perfect here because it lets a node know the sum of its children before calculating its own total sum.

---

Code

C++

class Solution {
public:
    const long long MOD = 1e9 + 7;
    long long total = 0;   // total sum of all nodes
    long long ans   = 0;   // best product found

    // First pass – compute total sum
    void calculateTotal(TreeNode* root) {
        if (!root) return;
        total += root->val;
        calculateTotal(root->left);
        calculateTotal(root->right);
    }

    // Second pass – post‑order, compute subtree sums and update answer
    long long subTreeSum(TreeNode* root) {
        if (!root) return 0;

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

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

        return leftSum + rightSum + root->val;
    }

    int maxProduct(TreeNode* root) {
        calculateTotal(root);      // O(N)
        subTreeSum(root);          // O(N)
        return ans % MOD;
    }
};

Python

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        self.total = 0          # total sum of all nodes
        self.ans   = 0          # best product found

        # First pass – compute total sum
        def get_total(node):
            if not node:
                return
            self.total += node.val
            get_total(node.left)
            get_total(node.right)

        # Second pass – post‑order, compute subtree sums and update answer
        def get_subtree_sum(node):
            if not node:
                return 0

            left_sum  = get_subtree_sum(node.left)
            right_sum = get_subtree_sum(node.right)

            cur_sum = left_sum + right_sum + node.val
            # Update max product (do NOT mod yet)
            self.ans = max(self.ans, cur_sum * (self.total - cur_sum))
            return cur_sum

        get_total(root)          # O(N)
        get_subtree_sum(root)    # O(N)

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

JavaScript

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxProduct = function (root) {
    let total = 0;   // total sum of all nodes
    let ans   = 0;   // best product found

    // First pass – compute total sum
    const getTotal = (node) => {
        if (!node) return;
        total += node.val;
        getTotal(node.left);
        getTotal(node.right);
    };

    // Second pass – post‑order, compute subtree sums and update answer
    const getSubtreeSum = (node) => {
        if (!node) return 0;

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

        const product = curSum * (total - curSum);
        if (product > ans) ans = product;

        return curSum;
    };

    getTotal(root);          // O(N)
    getSubtreeSum(root);     // O(N)

    // Use BigInt for safety before applying modulo
    return Number(BigInt(ans) % 1000000007n);
};

---

Key Takeaways

• Post‑order traversal is ideal when a node’s computation depends on its children (here we need subtree sums).
• Two‑pass strategy often simplifies problems: first gather global information (total sum), then perform the core logic (product calculation).
• Maximize before modulo – applying the modulo too early can change the ordering of products and give an incorrect answer.

---

Final Thoughts

As a mentor, I often see students struggle with tree problems because they try to visualize every possible split at once. Instead, focus on the property that cutting any edge isolates a whole subtree. By reducing the problem to “what is the sum of each subtree?” and using a simple post‑order walk, the solution becomes both intuitive and efficient. Happy coding! 🚀

Recursive Sum in Trees

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.