# 07.01.2026 [1339. Maximum Product of Splitted Binary Tree]
Max sumA*sumB of a tree split #medium
07.01.2026
1339. Maximum Product of Splitted Binary Tree medium blog post substack youtube
Join me on Telegram
Problem TLDR
Max sumA*sumB of a tree split #medium
Intuition
Find the total sum, then subtract each subtree to find the other sum.
Approach
we can calculate in 32 bit if use extemum of x = s/2
we can collect visited sums into a hashset
we can skip sums that are smaller than max/2
the fastest runtime speed is still calculation of x*(max-x) in-place
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(logn)$$
Code
// 11ms
fun maxProduct(r: TreeNode?): Long {
val a = ArrayList<Int>()
fun s(r: TreeNode?): Int = r
?.run {val s = s(left)+s(right)+`val`; a += s; s}?:0
val s = s(r); return a.maxOf {1L*it*(s-it)}%1000000007
}
// 3ms
pub fn max_product(r: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn s(r: &Option<Rc<RefCell<TreeNode>>>, res: &mut i64, max: &mut i32) -> i32 {
let Some(n) = r else { return 0 }; let n = n.borrow();
let s = s(&n.left,res,max)+s(&n.right,res,max)+n.val; *max = s.max(*max);
*res = (*res).max(s as i64*(*max - s)as i64); s
}
let (mut res,mut max) = (0,0); for _ in 0..2 {s(&r, &mut res, &mut max);} (res%1000000007) as i32
}