Maximum product of splitted binary tree

Tree Depth-First Search Binary Tree

55.5% acceptance

Feb 27, 2026

3573

120

Given the root of a binary tree, split the binary tree into two subtrees by removing one edge such that the product of the sums of the subtrees is maximized. Return the maximum product of the sums of the two subtrees. Since the answer may be too large, return it modulo 109 + 7. Note that you need to maximize the answer before taking the mod and not after taking it.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn max_product(root: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut subs = Vec::new();
    let total = Self::dfs(&root, &mut subs);
    let best = subs.iter().map(|&s| s as i64 * (total as i64 - s as i64)).max().unwrap_or(0);
    (best % MOD) as i32
  }

  fn dfs(node: &Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>, subs: &mut Vec<i64>) -> i64 {
    if let Some(n) = node {
      let b = n.borrow();
      let left = Self::dfs(&b.left.clone(), subs);
      let right = Self::dfs(&b.right.clone(), subs);
      let s = left + right + b.val as i64;
      subs.push(s);
      s
    } else {
      0
    }
  }
}