Maximum Product of Splitted Binary Tree -(Google, Meta, Amazon(Phone)) : Explanation ➕ Live Coding

[@prateekrath5098]

Brilliant explanation as always sir! please keep making the videos

[@codestorywithMIK]

Thanks a lot Prateek. I will for sure ❤️❤️❤️

[@manishv.8167]

Definately He is Awesome

[@codestorywithMIK]

Thanks a lot Manish ❤️❤️❤️

[@codestorywithMIK]

The time complexity of this one is a little straight forward. If you notice, we are visiting each node of the Tree just Once. So Time complexity will be : O(n) Where n = number of nodes in the tree. You can say we have called the function twice , - one for calculating totalSum - And another for calculating maximum product. So to be precise , Time complexity will be O(n +n) = O(2*n) which is effectively O(n) only. (Ignoring the constant 2). I hope that helped. Thanks to all of you for watching 😇

[@nagmakhan672]

The intuition and using same function to Update maxP was 🔥 🔥 🔥

[@souravjoshi2293]

Man this explanation is legit 🔥. You are seriously Hindi Version of NeetCode. Soon, you will be reaching millions of subs

[@piyushacharya7696]

Reach++ arey bhai kya ans hai🔥🔥🔥.

[@codestorywithMIK]

Thank you so much Piyush ❤️❤️❤️

[@oqant0424]

lesson learnt today: never judge a youtuber by his no of subscribers....... Man !!!!!!!!!!! u are a legit 🔥🙌

[@codestorywithMIK]

This comment made my day. I will sleep in peace Thank you so much ❤️❤️❤️

[@oqant0424]

@@codestorywithMIK i will thank myself today that i found your channel.......seriously

[@oqant0424]

@@codestorywithMIK please never stop making daily leetcode challenge solutions as your explanation will help a lotttttttttttt in logic building............literally no one on the whole youtube teaches how to build logic.....except u and the great Aditya Verma sir!

[@codestorywithMIK]

Means a lot ❤️❤️❤️

[@codestorywithMIK]

Sure thing. I will be there always ❤️

[@wearevacationuncoverers]

You are phenomenal. This channel is a treasure. please keep making the videos

[@debugging_life]

The intuition and explanation is amazing. It would be really helpful if you can explain how to calculate time complexities of such questions.

[@codestorywithMIK]

Thanks a lot Arpana. Actually the time complexity of this one is a little straight forward. If you notice, we are visiting each node of the Tree just Once. So Time complexity will be : O(n) Where n = number of nodes in the tree. You can say we have called the function twice , one for calculating totalSum And another for calculating maximum product. So to be precise , Time complexity will be O(n +n) = O(2*n) which is effectively O(n) only ignoring the constant 2. I hope that helped. Thank you again for watching 😇

[@debugging_life]

@@codestorywithMIK yes, It helped. Thanks !

[@souravjoshi2293]

Thumbnail me jo likha hai wo hi dekhkar maine like kar Diya

[@sounishnath513]

Baapre. You just gave the whole concept in just a minute. 😮😮. Seriously these videos are awesome ❤❤

[@codestorywithMIK]

Thank you so so much Sounish ❤️❤️❤️

[@pankajjangra7]

Bdhiya padhate ho bhai👌👌

[@codestorywithMIK]

Thank you so much Pankaj ❤️❤️❤️

[@oqant0424]

one earnest feedback :) plz discuss time and space complexities at the end!

[@codestorywithMIK]

Sure thing. Noted

[@yatri6329]

Hard h yaar , sum wala approach se easy ho gya, otherwise smjh nhi aa rha tha

[@souravjoshi2293]

True yaar. sum wala approach changed everything

[@anuppal3243]

Very nice and detailed explanation sir.

[@codestorywithMIK]

Thanks a lot Anup ❤️❤️❤️

[@gui-codes]

Awesome explanation

[@danianiazi8229]

Love the explanation

[@codestorywithMIK]

Thanks a lot 😇

[@madhuraj4you]

hatsoff

[@codestorywithMIK]

Thank you so so much Madhuraj ❤️❤️❤️

[@ramankr0022]

#awesome

[@varunsheth1003]

Nice explanation Sir !!!!

[@codestorywithMIK]

Thanks a lot Varun ❤️❤️❤️

[@shubhamsandanshiv515]

Greattttt

[@codestorywithMIK]

Thanks a lot Shubham ❤️❤️❤️

[@danianiazi8229]

I have just started question solving on leetcode and learning dsa but always I dont come up with approach like this

[@codestorywithMIK]

Hi Dania, it’s totally normal. We all get stuck. But with consistency and practice, we all can do great. Let’s do it 💪💪💪

[@YashSinghal]

Can we use the totalSum function to find the subTreeSum? this way we can keep find as void fn and no need to return

[@codestorywithMIK]

Hi Yash, Can you share the code. Sorry i am not able to follow 😇

[@YashSinghal]

@@codestorywithMIK I was thinking the wrong thing. It doesn't work

[@danianiazi8229]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int totalSum=0; int maxProd = 1; public int maxProduct(TreeNode root) { int totalSum = getTotalSum(root); int sum = findProduct(root); System.out.println("sum"+sum); return maxProd; } public int getTotalSum(TreeNode root){ if(root==null) return 0; int sum = root.val + getTotalSum(root.left)+getTotalSum(root.right); return sum; } public int findProduct(TreeNode root){ if(root==null) return 0; int subTreeSum = root.val + findProduct(root.left) + findProduct(root.right); int remainingSum = totalSum - subTreeSum; System.out.println(subTreeSum); System.out.println(remainingSum); System.out.println(remainingSum*subTreeSum); maxProd = Math.max(maxProd,remainingSum*subTreeSum); return subTreeSum; } } The same approach not working in java

[@codestorywithMIK]

I think you made some small mistakes. I have corrected your code. It works now : class Solution { int totalSum=0; int maxProd = 0; public int maxProduct(TreeNode root) { totalSum = getTotalSum(root); findProduct(root); return maxProd%(1000000007); } public int getTotalSum(TreeNode root){ if(root==null) return 0; int sum = root.val + getTotalSum(root.left)+getTotalSum(root.right); return sum; } public int findProduct(TreeNode root){ if(root==null) return 0; int subTreeSum = root.val + findProduct(root.left) + findProduct(root.right); int remainingSum = totalSum - subTreeSum; maxProd = Math.max(maxProd,remainingSum*subTreeSum); return subTreeSum; } }

[@yashchamoli8695]

good evening bhaiya can you plz provide the solution of 2049 leetcode as i am not able to understand how to make a tree from an array it is similar to today's question I would be thankful of you 🙏🙏🙏🙏🙏🙏

[@codestorywithMIK]

Hi Yash, Noted. I will soon add it Thanks for watching ❤️❤️❤️

[@ayushivishwakarma9101]

Bahiya maxp ko max product mai declare Kiya hai tho wo find k baad update kese hoga

[@harsh.jain22]

class Solution { public long maxProd = 0; public long totalSum; private static final int MOD = 1000000007; public int totalTreeSum(TreeNode root){ if(root == null) return 0; int LSum = totalTreeSum(root.left); int RSum = totalTreeSum(root.right); return LSum + root.val + RSum; } public int findingMax(TreeNode root){ if(root == null) return 0; int LSum = findingMax(root.left); int RSum = findingMax(root.right); int currSum = LSum + root.val + RSum; long prod = currSum * (totalSum - currSum); maxProd = Math.max(maxProd, prod); return currSum; } public int maxProduct(TreeNode root) { totalSum = totalTreeSum(root); findingMax(root); return (int)(maxProd % MOD); } }

[@shashwatchawla]

Why i am getting TLE for last two testcases , I also did it same way , can you please tell me what I am doing wrong ? class Solution { public: long long int sumSubtree(TreeNode* root,long long int &sum) { if(root==NULL) return 0; sum+=root->val; sumSubtree(root->left,sum); sumSubtree(root->right,sum); return sum; } long long int solve(TreeNode* root,long long int overAllSum) { if(root==NULL) return maxProd; long long int sum=0; long long int sumLower= sumSubtree(root,sum); long long int sumUpper = overAllSum-sumLower; long long int prod = sumLower * sumUpper; maxProd= max(maxProd ,prod ); solve(root->left,overAllSum); solve(root->right,overAllSum); return maxProd; } long long int maxProd=INT_MIN; int maxProduct(TreeNode* root) { long long int sum=0; long long int overAllSum = sumSubtree(root,sum); long long int l= solve(root->left,overAllSum); long long int r = solve(root->right,overAllSum); int ans = max(l,r) % (1000000007); return ans; } };

[@shashwatchawla]

Is it becz i am computing top to down and recomputing subtreesum everttime i come one level down ? :(

[@codestorywithMIK]

You have travelled the whole tree 3 times. May be that’s why

[@codestorywithMIK]

SumSutree Solve Solve

[@codestorywithMIK]

You can do it in 2 calls only. Like I mentioned in the video

[@shashwatchawla]

Yeah sir , thanks alot :)