Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

The input is a binary tree whose nodes contain positive integers. Exactly one edge must be removed, splitting the original tree into two smaller trees. Each smaller tree has a sum, and the goal is to choose the cut that maximizes the product of those two sums. The product must be maximized as an ordinary integer; only the final answer is reduced modulo $10^9 + 7$.

Trying every edge is unavoidable in the sense that any edge might be optimal, but recomputing both component sums from scratch for every cut would repeat most of the work. The useful observation is that every edge already defines a rooted subtree. Once that subtree’s sum is known, both sides of the cut are known immediately.

Deriving the optimal approach

Let the sum of the entire tree be $T$. Consider the edge from a parent to one of its children. Removing it separates the child’s whole subtree from the rest of the tree. If that subtree has sum $S$, then the other component has sum $T-S$, so this edge produces

$$ S(T-S). $$

This turns a tree-splitting problem into a subtree-sum problem. First compute $T$. Then process the tree in postorder, because a node’s subtree sum is simply its value plus the already-computed sums of its left and right subtrees. For every non-root node, evaluate $S(T-S)$; the node represents the edge between it and its parent.

The product is largest when the two component sums are as balanced as the available edges allow. That intuition is useful for checking an answer, but no search around $T/2$ is needed: one postorder traversal examines every possible cut exactly once and retains the best product.

The implementation below uses explicit stacks instead of recursive depth-first search. That matters because the tree can contain 50,000 nodes and may be shaped like a linked list, which can exceed Python’s recursion limit. It makes two linear passes and keeps only the active traversal frontier and completed child sums. The time complexity is $O(n)$ and the auxiliary space is $O(h)$, where $h$ is the tree height; in the worst case, $h=n$.

Python solution

from typing import Dict, List, Optional, Tuple


# LeetCode provides the TreeNode class.
# class TreeNode:
#     def __init__(
#         self,
#         val: int = 0,
#         left: Optional["TreeNode"] = None,
#         right: Optional["TreeNode"] = None,
#     ) -> None:
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    MODULUS = 1_000_000_007

    def maxProduct(self, root: Optional["TreeNode"]) -> int:
        """Return the largest product created by removing one tree edge."""
        if root is None:
            return 0

        total_tree_sum = self._sum_all_nodes(root)
        maximum_product = self._find_maximum_split_product(root, total_tree_sum)

        # The comparison must use full products; modulo is applied only once.
        return maximum_product % self.MODULUS

    @staticmethod
    def _sum_all_nodes(root: "TreeNode") -> int:
        """Compute the complete tree sum with an iterative depth-first search."""
        total = 0
        nodes_to_visit: List["TreeNode"] = [root]

        while nodes_to_visit:
            node = nodes_to_visit.pop()
            total += node.val

            if node.left is not None:
                nodes_to_visit.append(node.left)
            if node.right is not None:
                nodes_to_visit.append(node.right)

        return total

    @staticmethod
    def _find_maximum_split_product(
        root: "TreeNode", total_tree_sum: int
    ) -> int:
        """Evaluate every removable parent-child edge in postorder."""
        maximum_product = 0
        traversal_stack: List[Tuple["TreeNode", bool]] = [(root, False)]

        # Keys use object identity so this also works with unhashable TreeNode
        # implementations. Child entries are removed as soon as their parent
        # consumes them, keeping storage proportional to the active frontier.
        subtree_sum_by_identity: Dict[int, int] = {}

        while traversal_stack:
            node, children_processed = traversal_stack.pop()

            if not children_processed:
                traversal_stack.append((node, True))
                if node.right is not None:
                    traversal_stack.append((node.right, False))
                if node.left is not None:
                    traversal_stack.append((node.left, False))
                continue

            left_sum = (
                subtree_sum_by_identity.pop(id(node.left))
                if node.left is not None
                else 0
            )
            right_sum = (
                subtree_sum_by_identity.pop(id(node.right))
                if node.right is not None
                else 0
            )
            subtree_sum = node.val + left_sum + right_sum
            subtree_sum_by_identity[id(node)] = subtree_sum

            # Every non-root subtree corresponds to cutting its parent edge.
            if node is not root:
                remaining_tree_sum = total_tree_sum - subtree_sum
                split_product = subtree_sum * remaining_tree_sum
                maximum_product = max(maximum_product, split_product)

        return maximum_product

Interview follow-ups

Can the problem be solved with only one tree traversal?

A single postorder traversal can collect every subtree sum in a list. The last sum computed is the total tree sum, so a second pass over that list can evaluate $S(T-S)$ for every candidate. This is still $O(n)$ time, but it stores $O(n)$ sums even when the tree is balanced. The two-traversal solution above avoids that full list and uses $O(h)$ auxiliary space. The tradeoff is therefore one extra linear walk in exchange for potentially much lower memory use.

How would the solution return the edge that should be removed?

Each non-root subtree sum is associated with the node at the top of that subtree. When a product becomes the new maximum, retain that node as the selected child. The removed edge is the edge from its parent to that child. If the caller needs both endpoints, the traversal can carry the parent alongside each node or build a temporary identity-to-parent map. This does not change the $O(n)$ running time, but retaining all parent links takes $O(n)$ space; carrying the parent in traversal frames preserves $O(h)$ auxiliary space.

Why avoid the usual recursive postorder traversal?

Recursive postorder is concise and uses the same mathematical recurrence, but Python’s call stack is not designed for a worst-case chain of 50,000 nodes. Raising the recursion limit can merely move the failure from a Python exception to excessive native stack use. An explicit stack stores the same traversal state on the heap, handles balanced and skewed trees uniformly, and preserves $O(h)$ space without depending on interpreter settings.

What changes if node values may be negative?

The identity $S(T-S)$ still describes every cut, so enumerating all non-root subtree sums remains correct. The initialization must change, however: zero is no longer a safe lower bound because every valid product could be negative. Initialize the best value from the first valid cut, or use negative infinity, and continue comparing unreduced integer products. If the problem still requests a modulo result, apply it only after selecting the true mathematical maximum; reducing candidates early can reverse their ordering.

How would the approach minimize the difference between component sums instead?

For a cut with subtree sum $S$, the absolute difference is $|S-(T-S)|=|T-2S|$. The same total-sum pass and postorder traversal can therefore evaluate every cut, replacing the product comparison with a minimum-difference comparison. The proof is unchanged because each removable edge still corresponds to exactly one non-root subtree. Time remains $O(n)$ and auxiliary space remains $O(h)$.