Maximum Product of Splitted Binary Tree | LeetCode 1339 | DFS Tree Sum Optimal Solution

In this video, we solve LeetCode 1339 — Maximum Product of Splitted Binary Tree.

Code:
https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/solutions/7473561/easy-intuition-with-complete-logic-begin-v192

Upsolve Leetcode Contest:
https://youtube.com/playlist?list=PLsLlEdtakGoxoGbAwVRSlRjuB1yv1ycnc&si=_IDShX4wq0BxIkNf

Greedy & Heaps:
https://youtube.com/playlist?list=PLsLlEdtakGozAWFrLtFyKfzHL69QMdpkK&si=05iZsUB_hCmYZGPN

Two pointers:
https://youtube.com/playlist?list=PLsLlEdtakGow7Brk6c1OM_Bh-Mz55V7nX&si=hwShAQg6AT_VlwOm

Sliding Window:
https://youtube.com/playlist?list=PLsLlEdtakGozlKx_L-5PQJO-ua_maQb6R&si=hNoGQVZUI7OR9poU

Maths & Geometry:
https://youtube.com/playlist?list=PLsLlEdtakGoyWTBlOMC_mQ8Pv1M_pY2MX&si=MHwHo53uuirf26zC

Stack:
https://youtube.com/playlist?list=PLsLlEdtakGowhIcIi8uvWRy7Zw-bKoD85&si=9jvT_g2NQHFUHAMg

Set & Map:
https://youtube.com/playlist?list=PLsLlEdtakGozffR58V-u_qpYkwkR2Nc_F&si=_h2GBLEVi-hQyvI-

Bit manipulation:
https://youtube.com/playlist?list=PLsLlEdtakGowS_aAEQDNtNJA9zWkyk5uf&si=f0yO3hkGsorAhiod

Backtracking:
https://youtube.com/playlist?list=PLsLlEdtakGox7HMCBg3_sh8TrZoKnTPep&si=CMvDSFGzMRg6io1Y

Linked List:
https://youtube.com/playlist?list=PLsLlEdtakGowLdcT3ocFdt5MCEuTYVOzF&si=16QNR2HY_bLvVw2n

Binary Search:
https://youtube.com/playlist?list=PLsLlEdtakGozNxx5rfRgEW-1DYseLnDbV&si=RZ1BUYmSAvIvi5a5

Graph:
https://youtube.com/playlist?list=PLsLlEdtakGox1mdnH0PrJUhHJByUstkvx&si=JW-6qPw7zXDH-29j

Dynamic Progamming:
https://youtube.com/playlist?list=PLsLlEdtakGoyNROP7uWS9OLLHs9_JluVM&si=vJY6SxVXIHAbgzgk

You are given the root of a binary tree. You need to split the tree into two subtrees by removing exactly one edge such that the product of the sums of the two subtrees is maximized. Return the maximum product modulo 10^9 + 7.

------------------------------------
Approach:
------------------------------------
1. First, compute the total sum of all nodes in the tree using DFS.
2. Then, perform another DFS to compute the sum of every subtree.
3. For each subtree sum `s`, the other part will have sum = (totalSum - s).
4. Compute product = s * (totalSum - s) and keep track of the maximum product.
5. Finally, return the maximum product modulo 10^9 + 7.

We calculate the maximum before applying modulo to avoid losing precision.

------------------------------------
Complexity:
------------------------------------
Time Complexity: O(N) — each node is visited once.
Space Complexity: O(H) — recursion stack where H is the height of the tree.

------------------------------------
Problem Link:
https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/

#leetcode #leetcode1339 #binarytree #dfs #trees #treedp #subtreesum #coding #codinginterview #faang #dsa #algorithms #recursion #depthfirstsearch #interviewpreparation #softwareengineering #programming #javacode #cp #competitiveprogramming

Видео Maximum Product of Splitted Binary Tree | LeetCode 1339 | DFS Tree Sum Optimal Solution канала Study Placement