Maximum Product of Splitted Binary Tree

Medium
1947.

Maximum Product of Splitted Binary Tree

Maximum Product of Splitted Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Given the root of a binary tree, remove exactly one edge so that the tree falls apart into two subtrees, and make the product of the two subtrees' value sums as large as possible.

Return that largest product modulo 10^9 + 7. Note that you must maximise the product itself and only then take it modulo 10^9 + 7 — not maximise the remainder.

Example 1

Input
root = [1,2,3,4,5,6]
Output
110
Explanation
Cutting the edge above 2 gives parts summing to 11 (2 + 4 + 5) and 10 (1 + 3 + 6); 11 × 10 = 110 is the largest product.

Example 2

Input
root = [1,null,2,3,4,null,null,5,6]
Output
90
Explanation
Cutting above 4 splits the total 21 into 15 (4 + 5 + 6) and 6: 15 × 6 = 90.

Example 3

Input
root = [2,3]
Output
6
Explanation
There is one edge: 2 × 3 = 6.

Constraints

  • 2 <= number of nodes <= 5 · 10^4
  • 1 <= Node.val <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxProduct = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Product of Splitted Binary Tree — Problem & Solution

Maximum Product of Splitted Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Product of Splitted Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a binary tree, remove exactly one edge so that the tree falls apart into two subtrees, and make the product of the two subtrees' value sums as large as possible.

Return that largest product modulo 10^9 + 7. Note that you must maximise the product itself and only then take it modulo 10^9 + 7 — not maximise the remainder.

Example 1

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Cutting the edge above 2 gives parts summing to 11 (2 + 4 + 5) and 10 (1 + 3 + 6); 11 × 10 = 110 is the largest product.

Example 2

Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
Explanation: Cutting above 4 splits the total 21 into 15 (4 + 5 + 6) and 6: 15 × 6 = 90.

Example 3

Input: root = [2,3]
Output: 6
Explanation: There is one edge: 2 × 3 = 6.

Constraints

  • 2 <= number of nodes <= 5 · 10^4
  • 1 <= Node.val <= 10^4

Hints for Maximum Product of Splitted Binary Tree

  1. Hint 1

    Cutting the edge above a node separates exactly that node's subtree from the rest.

  2. Hint 2

    If the whole tree sums to T and the subtree to s, the product is s · (T - s). So you need T and every subtree sum.

  3. Hint 3

    Two walks: one for T, then a post-order walk that computes each subtree sum and tracks the best product. The product can exceed 32 bits — use 64-bit arithmetic and reduce modulo only at the end.

How to solve Maximum Product of Splitted Binary Tree

Every cut separates one subtree from the rest, so the candidates are s · (T - s) for every subtree sum s. Compute the total first, then all subtree sums in one post-order walk.

Approach

  1. Compute T, the sum of all node values.
  2. Walk the tree in post-order; for each node compute its subtree sum s = val + left sum + right sum.
  3. Update the best with s · (T - s) in 64-bit arithmetic.
  4. Return best mod (10^9 + 7).

Why it works

Removing the edge between a node and its parent leaves that node's subtree (sum s) and everything else (sum T - s); every edge is above exactly one non-root node, so every split is examined. The root's own sum gives the product 0 and never wins.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Taking the modulo before comparing products picks the wrong split.
  • T can reach 5 · 10^8, so the product reaches about 6 · 10^16 — overflow in 32-bit arithmetic, and past exact integers in a JavaScript double: there, choose the split whose s is closest to T / 2 (the product only grows as s nears half) and multiply once modulo the prime.

Reference solution

Python

from typing import Optional

def maxProduct(root: Optional[TreeNode]) -> int:
    sums = []

    def walk(node):
        if node is None:
            return 0
        s = node.val + walk(node.left) + walk(node.right)
        sums.append(s)
        return s

    total = walk(root)
    best = max(s * (total - s) for s in sums)
    return best % 1000000007

Java

public static int maxProduct(TreeNode root) {
    long total = sumTree(root);
    long[] best = {0};
    splitWalk(root, total, best);
    return (int) (best[0] % 1000000007L);
}

static long sumTree(TreeNode node) {
    return node == null ? 0 : node.val + sumTree(node.left) + sumTree(node.right);
}

static long splitWalk(TreeNode node, long total, long[] best) {
    if (node == null) return 0;
    long s = node.val + splitWalk(node.left, total, best) + splitWalk(node.right, total, best);
    best[0] = Math.max(best[0], s * (total - s));
    return s;
}

C++

long long sumTree(TreeNode* node);
long long splitWalk(TreeNode* node, long long total, long long& best);

int maxProduct(TreeNode* root) {
    long long total = sumTree(root), best = 0;
    splitWalk(root, total, best);
    return (int) (best % 1000000007LL);
}

long long sumTree(TreeNode* node) {
    return node ? node->val + sumTree(node->left) + sumTree(node->right) : 0;
}

long long splitWalk(TreeNode* node, long long total, long long& best) {
    if (!node) return 0;
    long long s = node->val + splitWalk(node->left, total, best) + splitWalk(node->right, total, best);
    best = max(best, s * (total - s));
    return s;
}

JavaScript

var maxProduct = function(root) {
    var total = sumTree(root);
    var state = { total: total, best: 0 };
    splitWalk(root, state);
    return mulMod(state.best, total - state.best, 1000000007);
};

var sumTree = function(node) {
    return node === null ? 0 : node.val + sumTree(node.left) + sumTree(node.right);
};

// Keeps the subtree sum closest to total / 2: s * (total - s) grows as s nears half.
var splitWalk = function(node, state) {
    if (node === null) return 0;
    var s = node.val + splitWalk(node.left, state) + splitWalk(node.right, state);
    if (Math.abs(state.total - 2 * s) < Math.abs(state.total - 2 * state.best)) state.best = s;
    return s;
};

var mulMod = function(a, b, m) {
    a %= m;
    b %= m;
    var hi = Math.floor(b / 65536), lo = b % 65536;
    return ((a * hi) % m * 65536 + a * lo) % m;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals