Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Removing an edge separates one child subtree from the rest of the tree. If its sum is s and the whole-tree sum is total, the product is s * (total - s). Thus every legal cut can be evaluated using subtree sums.

Approach

First compute the total node sum, then compute subtree sums in postorder. Python uses recursion and evaluates the two child-edge products at each node. JavaScript uses an explicit stack and evaluates the product for the completed subtree, corresponding to the edge above it. Its extra root evaluation gives zero, as do Python's missing-child evaluations; neither can beat a valid positive product. Track the maximum exact product and apply the modulus only after all comparisons, since taking remainders earlier could change which product is greatest.

# 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 get_total(node):
            if not node: return 0
            l = get_total(node.left)
            r = get_total(node.right)
            return l + r + node.val
        
        def test_edges(node):
            if not node: return 0
            l = test_edges(node.left)
            r = test_edges(node.right)
            self.res = max(self.res, l * (total - l), r * (total - r))
            return l + r + node.val
        
        self.res = 0
        total = get_total(root)
        test_edges(root)
        return self.res % (10**9 + 7)

Complexity analysis

For N nodes and tree height H, both solutions use O(N) time and O(H) auxiliary traversal space in the standard unit-cost model. Python integers and JavaScript BigInt preserve exact products before the final modulo. JavaScript uses explicit stacks. Python uses recursive traversals, so a legal 50000-node skewed tree can exceed the default recursion limit unless the runner raises it sufficiently.