Maximum Product of Splitted Binary Tree solution and explanation
Google
9 more videos on this problem
Maximum Product of Splitted Binary Tree | Simple Intuition | Leetcode 1339 | codestorywithMIKcodestorywithMIK · 29:44 · 15K views
Maximum Product of Splitted Binary Tree | Leetcode 1339 | Live coding session 🌳🌳🌳🌳Coding Decoded · 9:51 · 3K views
1339. Maximum Product of Splitted Binary Tree | Leetcode Daily - PythonLeetcode Daily · 8:37 · 1K views
Leetcode - Maximum Product of Splitted Binary Tree (Python)Timothy H Chang · 5:20 · 1K views
MAXIMUM PRODUCT OF SPIT BINARY TREE | LEETCODE # 1339 | PYTHON POSTORDER DFS SOLUTIONCracking FAANG · 9:43 · 991 views
Daily Leetcode #2108: Jan 07, 2026 - 1339. Maximum Product of Splitted Binary TreeProgramming Live with Larry · 6:07 · 553 views
Daily Leetcode #506: Aug 19, 2021 - 1339. Maximum Product of Splitted Binary TreeProgramming Live with Larry · 11:42 · 301 views
1339. Maximum Product of Splitted Binary Tree | JavaScript | LeetCode Daily Challenge | DetailedLeetCodeWithMonu · 13:13 · 290 views
Maximum Product of Splitted Binary Tree - Leetcode 1339 - PythonTim Huang · 4:45 · 217 views
Maximum Product of Splitted Binary Tree | Solution ExplainedTanishq Chaudhary · 12:22 · 214 views
The problem
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.
Example 1:
Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)
Example 2:
Input: root = [1,null,2,3,4,null,null,5,6] Output: 90 Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)
Constraints:
- The number of nodes in the tree is in the range
[2, 5 * 104]. 1 <= Node.val <= 104
Approach overview
Problem Overview: You are given the root of a binary tree. Remove exactly one edge so the tree splits into two subtrees. The goal is to maximize the product of the sums of the two resulting subtree values.
The key observation: if the total sum of the tree is S and a subtree has sum x, removing the edge above that subtree produces two parts with sums x and S - x. The product becomes x * (S - x). The problem reduces to computing every possible subtree sum and finding the split that maximizes this product.
Approach 1: Recursive Post-order Traversal (O(n) time, O(h) space)
This approach uses Depth-First Search with a post-order traversal of the binary tree. First compute the total sum of the entire tree. Then perform another DFS where each recursive call returns the sum of the current subtree. For each subtree sum x, compute the product x * (totalSum - x) and update the global maximum. Post-order works well because you need both left and right subtree sums before computing the current node’s sum. The recursion stack stores at most the tree height h, giving O(h) auxiliary space.
Approach 2: Iterative Post-order Traversal with Stack (O(n) time, O(n) space)
This version replaces recursion with an explicit stack while still performing post-order traversal on the tree. Nodes are pushed onto the stack and processed after their children, ensuring subtree sums are available before computing the parent sum. A hash map or dictionary stores intermediate subtree sums. Each node contributes exactly once to the total computation, keeping time complexity linear. This approach is useful in languages or environments where recursion depth could cause stack overflow or when you want tighter control over traversal order.
Both approaches rely on the same insight: compute subtree sums and evaluate the product for each possible edge removal. The final answer is returned modulo 1e9 + 7 as required by the problem.
Recommended for interviews: The recursive post-order DFS solution is what interviewers typically expect. It demonstrates strong understanding of subtree aggregation in trees and cleanly computes sums in a single traversal. Mentioning the iterative stack version shows deeper familiarity with traversal mechanics and recursion elimination.
Approach 1: Recursive Post-order Traversal
This method involves two main traversals of the tree:
1. Calculate the total sum of the tree using a post-order traversal.
2. During another post-order traversal, calculate the sum of each subtree and evaluate the potential product if split at that point.
import sys
sys.setrecursionlimit(10**6)
MOD = 10**9 + 7
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: TreeNode) -> int:
# Helper function to calculate total sum
def totalSum(node):
if not node:
return 0
return node.val + totalSum(node.left) + totalSum(node.right)
total = totalSum(root)
self.max_product = 0
# Helper function to calculate sub tree sums and max product
def findMaxProduct(node):
if not node:
return 0
sub_tree_sum = node.val + findMaxProduct(node.left) + findMaxProduct(node.right)
# Maximize the product of (total - sub_tree_sum) * sub_tree_sum
self.max_product = max(self.max_product, sub_tree_sum * (total - sub_tree_sum))
return sub_tree_sum
findMaxProduct(root)
return self.max_product % MODclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
public class Solution {
private long maxProduct = 0;
private long totalTreeSum = 0;
private static final int MOD = (int)1e9 + 7;
public int maxProduct(TreeNode root) {
totalTreeSum = totalSum(root);
findMaxProduct(root);
return (int)(maxProduct % MOD);
}
private long totalSum(TreeNode node) {
if (node == null) return 0;
return node.val + totalSum(node.left) + totalSum(node.right);
}
private long findMaxProduct(TreeNode node) {
if (node == null) return 0;
long subTreeSum = node.val + findMaxProduct(node.left) + findMaxProduct(node.right);
maxProduct = Math.max(maxProduct, subTreeSum * (totalTreeSum - subTreeSum));
return subTreeSum;
}
}#include <iostream>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
long totalSum = 0, maxProduct = 0;
const int MOD = 1e9 + 7;
public:
int maxProduct(TreeNode* root) {
totalSum = computeTotalSum(root);
computeMaxProduct(root);
return maxProduct % MOD;
}
long computeTotalSum(TreeNode* node) {
if (!node) return 0;
return node->val + computeTotalSum(node->left) + computeTotalSum(node->right);
}
long computeMaxProduct(TreeNode* node) {
if (!node) return 0;
long subTreeSum = node->val + computeMaxProduct(node->left) + computeMaxProduct(node->right);
maxProduct = max(maxProduct, subTreeSum * (totalSum - subTreeSum));
return subTreeSum;
}
};class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
const MOD = 1e9 + 7;
let maxProduct = 0;
let totalTreeSum = 0;
function maxTreeProduct(root) {
totalTreeSum = getTotalSum(root);
calculateMaxProduct(root);
return maxProduct % MOD;
}
function getTotalSum(node) {
if (!node) return 0;
return node.val + getTotalSum(node.left) + getTotalSum(node.right);
}
function calculateMaxProduct(node) {
if (!node) return 0;
let subTreeSum = node.val + calculateMaxProduct(node.left) + calculateMaxProduct(node.right);
maxProduct = Math.max(maxProduct, subTreeSum * (totalTreeSum - subTreeSum));
return subTreeSum;
}This solution performs a post-order traversal to first calculate the total sum of the tree. It uses another post-order traversal to calculate each subtree sum, and checks the product of the sum of the current subtree and the sum of the rest of the tree. The maximum product found during this traversal is returned.
Time Complexity: O(N), where N is the number of nodes. The algorithm performs a constant amount of work for each node.
Space Complexity: O(H), where H is the height of the tree. This space is used by the call stack during recursion.
Approach 2: Iterative Post-order Traversal with Stack
This approach uses an iterative post-order traversal using a stack to avoid recursion and concurrently calculate subtree sums and products. Carefully pushing nodes onto a stack and maintaining metadata to track progress and necessary calculations allow for this approach.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private const int MOD = 1000000007;
private long maxProduct = 0;
private long totalSum = 0;
public int MaxProduct(TreeNode root) {
totalSum = GetTotalSum(root);
Stack<(TreeNode node, long sum)> stack = new Stack<(TreeNode, long)>();
stack.Push((root, 0));
while (stack.Count > 0) {
var (node, subTreeSum) = stack.Pop();
if (node != null) {
long currentSum = node.val + subTreeSum;
if (node.left == null && node.right == null) {
maxProduct = Math.Max(maxProduct, currentSum * (totalSum - currentSum));
}
else {
stack.Push((node.left, currentSum));
stack.Push((node.right, currentSum));
}
}
}
return (int)(maxProduct % MOD);
}
private long GetTotalSum(TreeNode node) {
if (node == null) return 0;
return node.val + GetTotalSum(node.left) + GetTotalSum(node.right);
}
}This C# implementation uses a stack for iterative traversal in a post-order manner. With each loop iteration, it processes nodes and calculates sub-tree sums dynamically, treating the stack as a simulacrum for recursion. This allows for efficient computation without hitting recursion limits, and still evaluates maximum products as it iterates through subtree sums.
Time Complexity: O(N), due to each node being evaluated once by following its sequence to the stack until processed.
Space Complexity: O(H), where H is the height of the tree since the stack depth follows the path of the tree.
Approach 3: Two DFS
We can solve this problem with two DFS traversals.
In the first traversal, we use a sum(root) function to recursively calculate the sum of all nodes in the entire tree, denoted as s.
In the second traversal, we use a dfs(root) function to recursively traverse each node and calculate the sum of nodes in the subtree rooted at the current node, denoted as t. After splitting at the current node and its parent, the sums of the two subtrees are t and s - t respectively, and their product is t times (s - t). We traverse all nodes to find the maximum product, which is the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function maxProduct(root: TreeNode | null): number {
const sum = (root: TreeNode | null): number => {
if (!root) {
return 0;
}
return root.val + sum(root.left) + sum(root.right);
};
const s = sum(root);
let ans = 0;
const mod = 1e9 + 7;
const dfs = (root: TreeNode | null): number => {
if (!root) {
return 0;
}
const t = root.val + dfs(root.left) + dfs(root.right);
if (t < s) {
ans = Math.max(ans, t * (s - t));
}
return t;
};
dfs(root);
return ans % mod;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxProduct(root *TreeNode) (ans int) {
const mod = 1e9 + 7
var sum func(*TreeNode) int
sum = func(root *TreeNode) int {
if root == nil {
return 0
}
return root.Val + sum(root.Left) + sum(root.Right)
}
s := sum(root)
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
t := root.Val + dfs(root.Left) + dfs(root.Right)
if t < s {
ans = max(ans, t*(s-t))
}
return t
}
dfs(root)
ans %= mod
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn max_product(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
const MOD: i64 = 1_000_000_007;
let mut ans: i64 = 0;
let s = Self::sum(&root);
Self::dfs(&root, s, &mut ans);
(ans % MOD) as i32
}
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, s: i64, ans: &mut i64) -> i64 {
if root.is_none() {
return 0;
}
let node = root.as_ref().unwrap().borrow();
let t = node.val as i64
+ Self::dfs(&node.left, s, ans)
+ Self::dfs(&node.right, s, ans);
if t < s {
*ans = (*ans).max(t * (s - t));
}
t
}
fn sum(root: &Option<Rc<RefCell<TreeNode>>>) -> i64 {
if root.is_none() {
return 0;
}
let node = root.as_ref().unwrap().borrow();
node.val as i64 + Self::sum(&node.left) + Self::sum(&node.right)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Post-order Traversal | Time Complexity: O(N), where N is the number of nodes. The algorithm performs a constant amount of work for each node. Space Complexity: O(H), where H is the height of the tree. This space is used by the call stack during recursion. |
| Iterative Post-order Traversal with Stack | Time Complexity: O(N), due to each node being evaluated once by following its sequence to the stack until processed. Space Complexity: O(H), where H is the height of the tree since the stack depth follows the path of the tree. |
| Two DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Post-order Traversal | O(n) | O(h) | Best general solution. Clean implementation when recursion depth is manageable. |
| Iterative Post-order Traversal with Stack | O(n) | O(n) | Useful when avoiding recursion or handling very deep trees. |
Frequently asked questions
Is Maximum Product of Splitted Binary Tree easy or hard?
Maximum Product of Splitted Binary Tree is generally considered a medium difficulty problem. The traversal itself is straightforward, but recognizing that every subtree sum represents a possible split requires understanding how edge removal affects tree partitions.
Maximum Product of Splitted Binary Tree Python/Java solution
Python and Java solutions typically implement recursive post-order DFS. Each recursive call returns the sum of the current subtree while updating a global maximum product. The final result is returned modulo 1e9 + 7 after evaluating all possible subtree splits.
How to solve Maximum Product of Splitted Binary Tree in O(n)?
First compute the total sum of the entire tree using DFS. Then perform a post-order traversal where each node returns its subtree sum. For every subtree sum x, calculate x * (totalSum - x) and track the maximum product. Because each node is visited once, the algorithm runs in O(n) time.
What is the best approach for Maximum Product of Splitted Binary Tree?
The most efficient approach uses post-order depth-first search to compute subtree sums. After calculating the total tree sum, each subtree sum x is evaluated with the formula x * (totalSum - x). This checks the product created if the edge above that subtree is removed. The algorithm runs in O(n) time because every node is processed once.
Is Maximum Product of Splitted Binary Tree asked at Google/Amazon/Meta?
Tree and DFS problems with subtree aggregation frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of splitting trees or computing subtree metrics are common because they test understanding of depth-first traversal and recursive reasoning.
What data structure is used in Maximum Product of Splitted Binary Tree?
The problem primarily uses a binary tree along with depth-first search traversal. Recursive implementations rely on the call stack, while iterative versions use an explicit stack to simulate post-order traversal. Some implementations also store subtree sums in a list or hash map.
What is the time complexity of Maximum Product of Splitted Binary Tree?
The optimal solution runs in O(n) time where n is the number of nodes in the binary tree. A DFS traversal computes the total sum and all subtree sums in linear time. Space complexity is O(h) for recursion stack depth, where h is the tree height.