48 Diameter of a Binary Tree

[@zyro9922]

The day this guy releases Graph, companies will have to change the way they interview

[@Prakashsharma-hc2pe]

correct😃

[@livelypooja]

Can you suggest some good graph series in hindi

[@MohddAlii]

nazar laga di na

[@ritikyadav9378]

@@livelypooja Striver Graph series is enough!

[@deepakffyt2844]

​@@livelypooja have you completed graph ?

[@Ayushkumar-xj9vl]

No matter from which video you start , you will end up starting from the first video😂

[@siddheshbhujbal8838]

True 😁

[@adarshsrivastava9428]

thats what you call calculating from base case😂😂

[@sourabhdas6208]

correction: just 'return res - 1' as question asked for number of edges not nodes. This code is right. Just do 'return' as per question statement.

[@ashutoshraj7171]

thanks a lot , i am struggling with nodes

[@forbiddenumbrella]

here actually l and r are returning the heights of the left and right subtrees, not the diameters. Coz the diameter of the whole tree is basically the maximum value of (l + r + 1) for every node, this is what being done here.

[@zyro9922]

Yes absolutely

[@sairamakurti4808]

correct and thankyou

[@nabeelmehar2984]

Correct

[@tejasjoshi1907]

Correct

[@pranjalsinghmandloi8662]

Exactly

[@sarthakbhatia7888]

For those struggling with the leetcode questions.See Bhaiya is calculating the number of nodes and in leetcode you are asked number of edges so return res-1; class Solution { public: int solve(TreeNode* root,int &res) { if(root==nullptr) return 0; int l=solve(root->left,res); int r=solve(root->right,res); int height=1+max(l,r); res=max(res,1+l+r); return height; } int diameterOfBinaryTree(TreeNode* root) { if(!root) return 0; int res=INT_MIN; int x=solve(root,res); return res-1; } };

[@abhishekbajaj109]

res or *res plz clarify

[@sarthakbhatia7888]

@@abhishekbajaj109Here in the caller function we pass res and in the called function we have &res .This is call by reference.The changes made in the res o the called function will be reflected in the res of the caller function.

[@shivanshyadu4830]

thankyou so much bro for this information❤

[@gurshaan4848]

Thnks bhai😊

[@commentator2407]

Just change the way u r evaluating the diameter.. maxpath= max(maxpath, leftpath+ right path)

[@harpic949]

DP be like - Abe merako to andar le😂😂

[@shubhamshukla1506]

Key thing : diameter at each node is defined by 1 + lh (height of left tree) + rh (height of right tree). Just calculate that at each node to get the maximum diameter. Hence use the height method for binary tree and just add the line to calculate the diameter which gives the O(N) solution. The lines marked with --> are the extra lines for the diameter calculation. Rest is the good old height calculation method. Code : --> int ans = Integer.MIN_VALUE; int height(Node root){ if(root== null) return 0; int lh = height(root.left); int rh = height(root.right); --> ans = Math.max(ans, 1 + lh + rh); reurn 1 + Math.max(lh, rh); }

[@rushishinde9873]

correct

[@aishwaryshukla8880]

Anuj bhaiya also taught this method! But I didn't realise that time that this is DP. I still can't believe that we are doing DP without memoisation or tabularisation. But I understand that maybe we are using storage plus recursion that's why its DP

[@divyanshmishra5121]

complete code class Solution { public: int ans = INT_MIN; int height(Node * root) { if(root== NULL) return 0; int lh = height(root->left); int rh = height(root->right); ans = max(ans, 1+lh + rh); return 1 + max(lh, rh); } int diameter(Node* root) { height(root); return ans; } };

[@sameersharma8865]

In this code the number of nodes are being counted but we need to find (depth of left tree + depth of right tree). In this code a correction needs to be done. We have to return res-1 to ensure that we are not counting the top node of diameter.

[@sakshamsengar9798]

baki log to bs video dekh ke waah waah kie ja rhe...........khud se try kr ni rhe bs gyaan pele ja rhe comments me @AdityaVerma please pin this comment otherwise the solution is not submitting

[@vishaltk3013]

Yes. In the leetcode question, they have specified they need the number of "edges" in the longest path, not the vertices. Number of edges in a tree = number of vertices(nodes) - 1 // basic stuff: 2 nodes are required to make 1 edge, 3 nodes required to make 2 edges and so on. In the above approach what we are essentially calculating is the number of nodes, so in order to return the edge count, we simply reduce the answer by 1. Anyways, this is the best youtube channel to learn DP, period. Huge respect to Aditya. Below is the implementation of this solution in java. We don't need to pass "res" as a method arg, instead we can keep it as global variable class Solution { int finalAnswer = Integer.MIN_VALUE; public int diameterOfBinaryTree(TreeNode root) { func(root); // we don't need the output of this, as "finalAnswer" variable will have the answer return finalAnswer-1; // finalAnswer is the number of nodes, we need to return # of edges, hence -1 } int func(TreeNode node) { if(node == null) return 0; int lsum = func(node.left); int rsum = func(node.right); int toUpperLevel = 1 + Math.max(lsum, rsum); // we need to return this to previous call stack // we dont need to compare the lengths of paths going via current node or via parent node. // 1+lsum+rsum will always have larger value than 1+Max(lsum, rsum) . finalAnswer = Math.max(finalAnswer, 1+lsum+rsum); return toUpperLevel; } }

[@himanshusoni1512]

True, else we can update res as l+r instead of 1+l+r.

[@cryonim]

In a tree, by defn of tree, if there are n nodes, then there are n-1 edges, secondly any subtree in a tree is a tree. That means, the diameter subtree is a tree too, and you can easily switch between nodes/edges by using the n nodes, n-1 edges logic.

[@anjalisisodiya4093]

Thanks Aditya for great video lists. Diameter should be calculated as int temp=max(l,r)+1; res=max(1+l+r,res); no need to calculate ans

[@kamalrai286]

can you give me the java solution

[@a_mateur_photos]

Yeah. max(temp, 1+l+r) is always going to be 1+l+r anyways.

[@tanmayrauth7367]

Thanks... even I was confused during the explanation that why ans was calculated.

[@udayjordan4262]

exactly because my diameter is alwaya lh +rh +1 in all cases so res=INT_MIN; then we can find out only matter of fact is I need the maximum left height for root left and maximum right height for roots right so my induction return type will be 1+max(lh,rh); /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int solve(TreeNode* root,int& ans ){ if(root==nullptr){ return 0; } int lh=solve(root->left,ans); int rh=solve(root->right,ans); int temp=1+max(lh,rh); ans= max(ans,lh+rh+1); return temp; } int diameterOfBinaryTree(TreeNode* root) { int ans=INT_MIN; solve(root,ans); return ans-1; } };

[@vinayppandey4321]

True bruhhh

[@0anant0]

47 of 50 (94%) done! As others have mentioned comparing temp with 1+l+r is not reqd. Also, if we replace temp with what it truly is (height of cur node, max depth from cur node, etc.), then it would be clear. Similarly, ans = cur_dia

[@xCommandoEdits]

class Solution { public int solve(TreeNode root,int maxt[]){ if(root==null) { return 0; } int maxn=Integer.MIN_VALUE; int l= solve(root.left,maxt); int r= solve(root.right,maxt); int pass= 1+l+r; int notpass= 1+ Math.max(l,r); //height maxn= Math.max(pass,notpass); maxt[0]=Math.max(maxt[0],maxn); return notpass; } public int diameterOfBinaryTree(TreeNode root) { // int res=Integer.MIN_VALUE; int maxt[]={Integer.MIN_VALUE}; solve(root,maxt); return maxt[0]-1; }

[@amanprateek3265]

This is a pure recursive solution. Where we use DP in this question

[@pranshujain6752]

we can convert this in dp easily .... if you have seen previous video's

[@deeproy2719]

bhai...kaha the tum... mai pareshan ho gaya tha ki ye dp kaise hua... yeh to recursion hua hai waise hum node aur diameter ka map banake kar sakte hai dp me

[@arpangoyal9947]

How we use dp in it because we visit every node only one time so what is need of memoization because we never need to call visited node again??

[@amol_]

In my knowledge this video is little misleading, actually dp problem tree can be LCA based queries on tree. Same we can use jump pointer to answer efficiently this concept known as binary lifting. Other problems also exist on same line

[@prachi1807]

for ans, why are you evaluating it as max(temp, 1+l+r). 1+l+r will always be greater than temp right?

[@naro.tam_]

ofcourse

[@kumarimanisha5506]

Plus diameter is from leaf to leaf right. So I don't think we should compare temp as temp is only from some leaf (other from left or right) to the current node. So there is no sense to include this path because it is not from leaf to leaf. And of course your reason is logical.

[@ankitranjan88]

For without including root node

[@divyanshuupadhyay9831]

exactly.. it will always be greater than or equal to temp

[@Rishi441]

yess, But Understand the intuition of Aditya verma for his whole dp series he write one code and do little bit changes for further upcoming same pattern question

[@maktimizetech]

Logic - Base Condition -> Stop when the node is null by returning 0. Main Logic -> You are supposed to find the max diameter at each node and update the variable which stores the max diameter found till that point, 'diameter' in the logic below. 1. At any node you can find the diameter by doing (1 + left + right), and then comparing if it is the max diameter till that point of time. If yes, store it in the 'diameter' variable. 2. Returning (1 + max(left,right)) to it's parent call to let parent node also calculate the diameter on similar lines as mentioned in step 1. Why max(left,right) ? As parent won't require both but just the path/height/depth that gives max value. In the end the 'diameter' variable would hold the answer. ------------------------------------------------------------------------------------- Java code - private static int diameter = Integer.MIN_VALUE; private static int getDiameter(Node node){ //Base condition if (node == null) return 0; //Main logic int left = getDiameter(node.left); int right = getDiameter(node.right); int diameterAtCurrentNode = 1 + left + right; diameter = Integer.max(diameter, diameterAtCurrentNode); return (1 + Integer.max(left,right)); }

[@yashikagupta3963]

He has power to give the exact words to every single possible doubt.

[@kalagaarun9638]

For those with doubtsaying max(l,r)+1 will always be < 1+l+r: This code works perfectly fine : int diautil(Node *n,int &res){ if(n==NULL)return 0; int l=diautil(n->left,res),r=diautil(n->right,res); res=max(l+r+1,res); return max(l,r)+1; }

[@sakshigupta7616]

root = 1, left = -1, right = -2.... 1 + -1+-2 = -2 and 1 + max(-1,-2) = 0....so in this case 1 + l +r is less than temp. But I think this can not be the answer as diameter is between two leaves, and in this case one node would not be the leaf so actually the statement is not only redundant but wrong! It would give wrong answer for test cases like I have shown you. Your code would be right then!! What do you think?

[@sudeepchowdhary2577]

@@sakshigupta7616 But the left and right represents the no. of nodes in left subtree and right subtree, so the value of left and right can't be negative. Their minimum value can be zero if no nodes are present. (which is coming from our base condition).

[@rahulrewale6195]

The second line in induction step is not required. You are taking max between (1+l+r) and temp, which is 1+max(l, r). So, the result will always be (1+l+r). Induction: # calculate current diameter dia = 1 + l + r # if the current diameter is greater than the previously computed diameters, update res = max(res, dia) # return the height to parent node return 1 + max(l, r)

[@TheBillionairesWorld]

Yes you are right

[@shivompandey8260]

bro value of temp always remain less than or equal to 1+r+l but why have we taken max(temp,1+r+l) as ans

[@rupalitiwari5012]

comparing temp with 1+l+r is redundant. I have tried to solve the code without using this line and it worked. Simply store 1+l+r in ans.

[@raviagrawal8328]

True, but I think he's establishing a general format for the induction section so that it's easier to remember. See the next video where it becomes important to do the max of temp and result at current root.

[@adeshpradhan1314]

int ans = max(temp, 1+l+r) is not required , ans = 1+l+r will work great video BTW

[@kalagaarun9638]

then what is the use of temp and what will be its use if it only returns height of the tree ??

[@shubhamthind8286]

@@kalagaarun9638 we are returning height from the function, but we are calculating the diameter in res variable... That res variable is passed by reference, that's why we will have the final answer in it when we return to main function. We are returning height, because we need left and right height to calculate diameter

[@codeit8320]

dude it might be his general syntax, I accept it is redundant but not wrong , its his way of solving tree with this general syntax , might help later... :)

[@nitishmishra9943]

@@codeit8320 Exactly

[@anamikaahmed4887]

Way better explanation than striver or Anuj bhaiya!

[@shrishtysrivastava9282]

Best content 👍 Please make series on graph and hashing.

[@sujoyseal195]

I think left subtree and right subtree for any given node should return the depth and not diameter . The left subtree should return left depth and right subtree should return right depth . Then you can return 1+ max(leftdepth, right depth) which will contribute to the diameter in the case where the given node doesn't want to become the root of the diameter path. Bro, I think you should revise the video. It's not possible for left subtree to return left diameter since once you say DIAMETER you have already FIXED the end leaves. So no question of returning. Same goes for right subtree. Please follow the comment section where many people are addressing the same issue. Please address this issue and clear the confusion because I think your video on diameter is misleading students.

[@pranavsingh1081]

True 🥲

[@kushalgupta9613]

The comment section is full of confusion but the explanation is correct. I've verified it by drawing the tree and traverse each and every node. If you have any issue, reply on this comment. I will try my best to explain!

[@subhamthakur565]

yeah the answer is correct.... but temp we re returning is height not the diameter .. i.e the value store in l,r are height not diameter.

[@bandit7348]

Waah bhai....kahi pr bhi samaj nhi aa rha tha....ye video me mast samaj aa gaye

[@siddharth.chandani]

I don't know why we are comparing *temp and (1+l+r)* in *ans* because (1+l+r) will always > temp... { temp= max(l,r) +1 }

[@piyushji2312]

Aditya bhai isme memoize nahi karenge kya ? Plz reply !

[@abhilashasaini8758]

Best solution of diameter of bt, thankyou! why are we calling this dynamic programming tho?

[@swapnabiswal8754]

I have the same doubt. Can anyone clarify??

[@vsrproduction1875]

Thanks man🙏🙏 you have done really a great job for a student like me who think dp as nightmare .

[@HarmonicQuest]

Temp is max of (l and r) + 1 and so temp will be less then or equal to l+r+1 always . Ans is simply l+r+1

[@abhinandanb3591]

Answer for the leet code question, in leetcode they ask for number of edges which does not include the starting node, whereas in this question in the video we are including the starting node as well, so to answer the leetcode question just subtract 1 from final result leetcode.com/problems/diameter-of-binary-tree/ /** * 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 result = Integer.MIN_VALUE; public int diameterOfBinaryTree(TreeNode root) { solve(root); return result-1; } public int solve(TreeNode root) { if(root == null) { return 0; } int left = solve(root.left); int right = solve(root.right); int temp = 1 + Math.max(left, right); int ans = Math.max(temp, 1 + left + right); result = Math.max(result, ans); return temp; } }

[@monke890]

bruh -_-

[@umangaggarwal2017]

Concept Understanding k liye lecture is perfect! Respect++; // Correct Code int solve(TreeNode* root, int &res) { if(root == NULL) return 0; int l = solve(root->left, res); int r = solve(root->right, res); int temp = 1 + max(l,r); res = max(res, l + r); return temp; }

[@maarengenai465]

"Apan" mil kar seekhenge.. great content

[@rishabhkesarwani5761]

for Java Guys ... We As Java don't support Pass by reference.. So we need to create a new Class that is to be passed.. class Solution { // Function to return the diameter of a Binary Tree. class A{ int val=Integer.MIN_VALUE; } int diameter(Node root) { A res=new A(); solve(root,res); return res.val; } int solve(Node root, A res){ if(root==null){ return 0; } int l=solve(root.left,res); int r=solve(root.right,res); int temp=1+Math.max(l,r); int ans=Math.max(temp,1+r+l); res.val=Math.max(res.val,ans); return temp; } }

[@ravishraj664]

Thanks man

[@stepup7052]

@@ravishraj664 or we can pass 1 size array and store ans in it

[@abhishekrajanofficial]

We can use single sized array or AtomicInteger, in case of AtomicInteger use set() method to set the value and while returning the value use get() method

[@aniketkarna]

Guys don't confuse height with diameter, height is no. of edges and diameter in this video is no of nodes. So, in any question they will tell what parameter we are to find and whether it is no of nodes or no of edges.

[@Viralmems_xyz]

bhai tujhe kisi ne pucha kyu gyan bat rha hai

[@harinath_mishra]

thanks sir for providing dp series

[@ajaysrivas6791]

Wouldn't l + r + 1 always be greater than max(l,r) + 1 ? I think the line "int ans = max(temp, 1 + l + r) is not required at all because of the fact i mentioned.

[@himanshutejan4275]

Yes

[@kanakmittal3756]

I tried both recursive and recursive with memo (using maps). The time taken by simple recursion - 0.3s, time taken with memo - 0.9s.

[@swakal8868]

try for really large trees. then u will see difference.

[@richeshc]

@@swakal8868 solution accept ho gaya?

[@jswlprtk]

Where is the repeated work mate? Is the memo ever used? 😂😅

[@jain007neeraj]

public static int fetchDiameter(TreeNode root) { if (root == null) { return 0; } int nodesInLeft = fetchDiameter(root.left); int nodesInRight = fetchDiameter(root.right); // If this node is not the actual root. // then we have to send to root, what is the max // number of nodes i can calculate from here. int temp = 1 + Math.max(nodesInLeft, nodesInRight); // Now let's check if this "node" can actually contribute // to the diameter. int answer = Math.max(temp, 1 + nodesInLeft + nodesInRight); // We have to check this at every node // since max diameter can go through any node in the tree. DIAMETER = Math.max(DIAMETER, answer); return temp; } Full Program on : github.com/neerajjain92/data-structures/blob/master/src/com/leetcode/year_2020/DP/dynamic_programming_on_trees/DiameterOfBinaryTree.java

[@mayur_madhwani03]

ans = 1+l+r will also work here because temp is always going to be less

[@prabhatpandey1638]

Diameter of binary tree is : Max height of left node + Max height of right node + 1 (Current node itself) This will resolve the confusion as per why were are calculating Math.max(left,right)+1 in Temp variable. Although Answer variable is not really needed and added some confusion , Here is the simple code snippet private static int solve(Node root) { //Following two code blocks will always be fixed. if(root==null){ return 0; } int left = solve(root.left); int right = solve(root.right); //Calculating height of Node to retrieve the longest path int longestPathOfNode = Math.max(left,right)+1; //Update diameter when you find a bigger one diameter = Math.max(diameter,1+left+right); //Return the longest path which could be either left or right path for next calculation. return longestPathOfNode; } ^^ We are updating diameter when we find a bigger one that is all.

[@--Blood--Prince--]

Diameter will be passed as function argument right?

[@bite091_jamee7]

Amazing lecture

[@pavankumar-cy6mg]

my observations 1. diameter at any node is l+r+1 where l is height of left subtree and r is height of right subtree, 2. if i return height of node at any point would be sufficient what aditya teaching is complex res=max(res,l+r+1); return max(l,r)+1;

[@tanujaSangwan]

I agree. Couldn't visualise or understand it. He doesnt dry run the dp or recursive solution

[@sachetansabhahit6235]

At 6:05 you said "left diameter milega and right diameter milega" but I think you meant height , correct me if I'm wrong. Thanks

[@swagatdas1991]

Aditya Verma: No, since diameter represent the number of nodes--> it selects the best among left and right (thats why max(l,r)) and then add one because of itself (counts itself) and then pass it further. I hope that clears your doubt. Thanks !!

[@swagatdas1991]

Myself Charam (another comment I found useful) : To make things clear, the diameter of tree = max{ (lheight + rheight+1) for each and every node}. so our function actually returns the height of tree rooted at 'root'. res stores the max(lheight+rheight+1) and we traverse every node

[@shivagupta138]

Since there is no pass by reference in java, we can achieve the same by passing an array as follows - "class Solution { public int recursive(TreeNode root, int[] result){ if(root==null){ return 0; } int left_height=recursive(root.left,result); int right_height=recursive(root.right,result); int temp=Math.max(left_height,right_height)+1; int ans=Math.max(left_height+right_height+1,temp); result[0]=Math.max(result[0],ans); return temp; } public int diameterOfBinaryTree(TreeNode root) { int [] result=new int [1]; recursive(root,result); return result[0]-1; } }"

[@ashutoshsoni7439]

can u please made a video on LIS , DP on grid , and kadane's algorithm

[@TheAdityaVerma]

Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️

[@GauravVerma-hd4cf]

​@@TheAdityaVerma, As the June is going on can you please upload the remaining videos ASAP.

[@Vishal-242]

@@TheAdityaVerma 10 months later , we are still waiting

[@vishesh_soni]

@@TheAdityaVerma 1 year later and we are still waiting

[@abhishekhorton79]

@@TheAdityaVerma it's may please upload ;)

[@anssha2643]

can you make some more videos on trees? Your explanation is the best so far I have seen on any videos or text books

[@priyanshuranjan2001]

for those who are struggling on gfg:- int solve(Node* root,int &res) { if(root==nullptr) return 0; int l=solve(root->left,res); int r=solve(root->right,res); int height=1+max(l,r); res=max(res,1+l+r); return height; } int diameter(Node* root) { if(!root) return 0; int res=INT_MIN; int x=solve(root,res); return res; }

[@KUSHALLOYA]

Great video Bhaiya, just a correction, we can simply store (1+l+r) to the ans instead of storing max(temp,1+l+r) as (1+l+r) would always be greater than temp which is 1+max(l+r)

[@ketanmehtaa]

this is the way for dp solution which u can use class Solution { public: pair diameterOfBinaryTre(TreeNode* root) { // base case if(root==NULL) { pair p; p.first =0; p.second=0; return p; } pair opt1= diameterOfBinaryTre(root->left ); pair opt2= diameterOfBinaryTre(root->right); int opt3=opt1.first+opt2.first; int height = max(opt1.first,opt2.first)+1; pair output; output.first=height; output.second=max(opt1.second,max(opt2.second,opt3)); return output; } int diameterOfBinaryTree(TreeNode* root) { return diameterOfBinaryTre(root).second; } };

[@joshithmurthy6209]

thanks for the video

[@swagatpatra2139]

int maxDia; int diameter(TreeNode root) { diaHelper(root); return maxDia; } int diaHelper(TreeNode root){ if(root == null) return 0; int left = diaHelper(root.left); int right = diaHelper(root.right); maxDia = Math.max(maxDia, left + right+1); return Math.max(left,right)+1; }

[@varsha9094]

why are we returning temp instead of res??

[@pankajkhushalani]

Solution of diameter of a tree using height helper function (as submitted on GFG): int height(Node* child) { if (child == nullptr) return 0; return 1+max(height(child->left), height(child->right)); } int diameter(Node* root) { if (root == nullptr) { return 0; } int root_path = height(root->left) + height(root->right) + 1; int left_path = diameter(root->left); int right_path = diameter(root->right); return max(root_path, max(left_path, right_path)); } Hope it helps! Thank you Aditya sir for the amazing content that you put out for free! It really really helps.

[@anmol-gupta]

There is a small mistake at 13:25. For the final answer, we have to return "res - 1" instead of "res" because we do not want to count the root node of the longest path. If you don't understand what I mean, try doing this question on LeetCode.

[@zetaro7943]

We will count for the root node But we want to calculate longest path which on leetcode mentioned as max number of edges between two nodes, that's why we need to return (res-1).

[@Finimals]

In code condition to calculate "ans" is not required because its ans = Max(temp, (l+r+1)); but we know temp is temp = max(l,r) +1; which makes ans = Max(max(l,r)+1, l+r+1) so the "l+r+1" will always be max unless any one is negative, so unless questions considering weights we dont need the step.

[@shivammaniharsahu1228]

sir awesome explanation sir after every code you should also tell time complexity of that optimized code it will be a great help

[@anamikaahmed4887]

Java Code: class Solution { int maxValue = Integer.MIN_VALUE; public int diameterOfBinaryTree(TreeNode root) { height(root); return maxValue - 1; } private int height(TreeNode root) { if (root == null) return 0; int left = height(root.left); int right = height(root.right); // Calculate the height of the current subtree rooted at 'root' int temp = 1 + Math.max(left, right); // Calculate the potential diameter of the current subtree // rooted at 'root' (passing through 'root') int answer = Math.max(temp, 1 + left + right); // Update 'maxValue' with the maximum diameter found so far maxValue = Math.max(maxValue, answer); // Return 'temp' as the height of the current subtree rooted at 'root' return temp; } }

[@anil7931]

Now i can find area of binary tree as well :P

[@sanchitkaul5084]

Correction _____-------______----- return res-1;

[@hanumansidh2287]

95K congrats

[@abhinavgarg3013]

Your content so good bro ..

[@adityaagarwal5348]

How DP is used here? We are not storing any values or reusing the calculations done in previous recursion calls? is returning temp working here as DP?

[@AkshatChaudhary-fe3vv]

Verma ji ne extra views k liye trees k problems ko dp ki playlist mei daal diya. Business karo toh bada karo Purshotam bhai

[@arpitverma8060]

Excellent Bro!!!!!!

[@ajitdhayal1612]

Bhaiyya, we can do it in this way too temp=1+max(l,r) Int ans=1+l+r res=max(res,ans) return(temp)

[@mainaksanyal9515]

Exactly, mujhe wohi nhi samajh aa raha tha akhir ans=max(temp,1+l+r) karne ki kya zarurat hai, kyuki ans toh humesha 1+l+r hi hoga. temp toh kabhi 1+l+r se bada ho hi nhi sakta!

[@sumitkumarverma313]

@@mainaksanyal9515 yes 1+max(l,r)=0,r>=0 ;

[@satishbahuguna3349]

Plz make such vedios for graph and tree using recursion 🙏 @aditya

[@nikhilraj5115]

Am i the only one whose answer is coming wrong using this approach 🤔

[@Shorts_n_Laughs]

How this topic will come under DP? isn't it just pure recursion? we are not storing and value to avoid calling same function, although we will not call same function in here it will be O(N) solution.

[@dteentitan]

Brilliant!! Not sure if I would've understood if someone else had explained it to me.

[@Vishnu-lw3jv]

In some qs like in leetcode they ask diameter as no of edges instead of no of nodes so in that case just remember that ( no of edges =no of vertices -1) so return ans-1

[@gta6515]

Thank you so much for clearing.

[@techandconsole]

@@gta6515 I literally searched for "leetcode" on the page just to see if I am the only one who had this problem while running the algo on leetcode and found your comment. :P. Thanks for explaining I also was not getting the right answer (Y)

[@shubhankartripathi4840]

Bhaiya 1+l+r to temp se hamesha bada hoga to usko i think redundant kar sakte

[@banerjeetathagat]

Woi mai bhi soch raha tha rather just res me max updation se ho jaega kaam i think

[@ajitdhayal1612]

Sirf 1+l+r hee ans mein assign ker do . Tum sai ho!!!

[@learnwithdeepak6804]

There is no dp used right? We are not storing data.

[@priyapurohit2626]

Excellent explaination. Just one question, the variable temp will store diameter or height?

[@TheAdityaVerma]

Thanks priya !! It is storing the diameter.

[@svworld01]

@@TheAdityaVerma how ? 1+max(l, r) is height sir. I think ans variable is storing diameter.

[@yashrathore9427]

@@TheAdityaVerma it should be the height

[@deepjyotsinghkapoor1955]

@@yashrathore9427 1+max(l,r) gives diameter....please note: l and r are not the heights of left and right subtree.....instead they will give diameter of left subtree and right subtree respectively.

[@adeshpradhan1314]

@@deepjyotsinghkapoor1955 l and r gives max height of left and right subtree, so temp is max height, as you can also see, we are returning res as our final diameter and not temp ( which is max height) got submitted on gfg

[@sujoyseal195]

Can you run this code on leetcode and pass all test cases ? It's not diameter...it's height. You can never add 1 to diameter since diameter already includes all nodes in the max path. Please post code link here.

[@vaibhavtiwari6540]

return solve(*root,&res) if you want the #nodes in the longest path, and return solve(*root,&res)-1 if you need #edges in the longest path. Happy coding!!

[@richeshc]

Functional Python code following video explanation class Solution: def getMaxDiameter(self, node, res): if node is None: return 0, res left, res = self.getMaxDiameter(node.left, res) right, res = self.getMaxDiameter(node.right, res) # if node is part of solution temp = max(left, right) + 1 # if node is solution ans = max(temp, left+right+1) res = max(res, ans) return temp, res #Function to return the diameter of a Binary Tree. def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: # Code here import sys res = -sys.maxsize temp, res = self.getMaxDiameter(root, res) return res-1

[@hrithikraj6658]

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int find_diameter(TreeNode* root,int&result){ if(!root) return 0; int left = find_diameter(root->left,result); int right = find_diameter(root->right,result); int not_going_throught_it = max(left,right)+1; int going_throught_it = left+right; /*max(not_going_throught_it, 1+left+right);*/ result = max(result,going_throught_it); return not_going_throught_it; } int diameterOfBinaryTree(TreeNode* root) { int result = INT_MIN; if(!root) return 0; find_diameter(root,result); return result; } };

[@hrithikraj6658]

you can add 1+left+right to count the number of nodes

[@Yadav_sunil_02]

How to minimize tree diameter by removing atmost k edges?

[@shubhamvishwakarma3205]

Why are we returning temp in the solve function...not res? as res holds the max value

[@arpitanand4248]

Sir , in hypothesis part , you are treating l and r as diameters but in induction part, you are treating l and r as heights . Please clear my confusion !

[@Ayushkumar-xj9vl]

l and r are heights. At every node, in temp, we are storing the max height, which can be from either left or right. Then in variable named ans , we are storing the diameter possible taking current node as root. Then we are comparing the diameter with res and updating it ,in case the current answer is greater than res

[@anushree3744]

How is it DP? we are not using any cache here...

[@namanjain9922]

For Java user I coded this But still confused why there is need of creating "Res" class any expert here int diameter(Node root) { // Your code here Res res = new Res(); res.val = Integer.MIN_VALUE; solve(root,res); return res.val; } public static int solve(Node root,Res res){ if(root==null){ return 0; } int l=solve(root.left,res); int r=solve(root.right,res); int temp=Math.max(l,r)+1; int ans=Math.max(temp,l+r+1); res.val=Math.max(res.val,ans); return temp; } } class Res { public int val; }

[@rohitlandge3890]

correction: ans = l + r

[@tejasharishborkar3754]

I don't understand one thing i,e where is DP used in it...this is normal recursive code??

[@abhinavghosh725]

yes i agree ! this is regular recursion no dp involved here!

[@pruthvirajk6019]

Dp is involved dude....How ? Each recursive call of subtree is returning a answer to top part of tree,it means that we are building the tree from bottom to top and the answers computed at the bottom are passsed to the top,Anyways it its not stored in seperate table since those temp and res are themselves getting updated in each call.

[@trinanjannandi3888]

DP doesn't always means that you will need a data structure to store all the values for every level. If you can pass a calculated value from one level to another then also its kinda DP

[@radhikagarg269]

Sir aapne temp meh 1 add kr liya ...matlab parent ko include kr liya ...toh fr ans meh kyu krna h +1 ....jab parent ko max of left and right lete time he include kr rheh h

[@artsmart9769]

u can simply do this, BTW great tutorial loved it !! public int getMaxPathSumBT(TreeNode node) { if(node == null) return 0; int rightSum = getMaxPathSumBT(node.right); int leftSum = getMaxPathSumBT(node.left); int currentPathSum = node.val + Math.max(leftSum, rightSum); int currentMax = Math.max(currentPathSum, node.val + leftSum + rightSum); sum = Math.max(sum, currentMax); return currentPathSum; }

[@sairajdas6692]

how is this dp?

[@shwetanksingh5208]

Where is dp in this?

[@rishikumar-rk7tk]

Can you explain pointer and reference in the middle of your video it won't take too much time please ... I have some confusion on this topic Please...

[@rohitvishwakarma1238]

543. The diameter of Binary tree (Leetcode) Followed the same method but we need to do a little change here. In the leetcode test cases, they are not considering the root as the part of the binary tree. Strange though. So wee have to just subtract -1 from the result. class Solution { int result=1; public int diameterOfBinaryTree(TreeNode root) { if(root==null) return 0; solve(root); return result-1; } public int solve(TreeNode root){ if(root==null) return 0; int left=solve(root.left); int right=solve(root.right); int temp=1+ Math.max(left,right); int ans=Math.max(temp,left+right+1); result=Math.max(result,ans); return temp; } }

[@santasingh9045]

This is because they are considering edges and number of edges in a tree are (number of nodes -1), while we are computing our answer based on nodes. So this is the reason we have to subtract 1 from our final result.

[@vibekdutta6539]

say that V is the node and v1 is a child of V, now for v1 it returns temp to its parent ie V, we know temp is storing the result in which the diameter is not passing through v1, say v1 returns temp=5 to V, now ans for V say is 7 and so is the res, but problem is that what if the child v1's ans=9 ie the ans in which v1 is passing through the diameter, then in this case the final answer is 9 but we'll get 7 as for root node ie V we are returning ans to the main method..... please explain.

[@sabujjana2860]

You are saying that hypothesis returns the diameter. Then how can you add 1 to Max(l, r). You should add 1 to the max height of left and right subtree, not the diameter.

[@TheAdityaVerma]

No, since diameter represent the number of nodes--> it selects the best among left and right (thats why max(l,r)) and then add one because of itself (counts itself) and then pass it further. I hope that clears your doubt. Thanks !!

[@charan775]

To make things clear, the diameter of tree = max{ (lheight + rheight+1) for each and every node}. so our function actually returns the height of tree rooted at 'root'. res stores the max(lheight+rheight+1) and we traverse every node

[@thinklessdomore4549]

Hi Aditya! Awesome content.. this will be breaking the internet soon.. ! Just one point on this video.. the temp Value returned by the recursive functions should be the height.. and not the diameter. Diameter should only be used to update the result ..

[@sujoyseal195]

This should be height and not diameter

[@akarshjain25]

can you please explain why we are returning ans or temp ans in tree questions (i mean why tempans here and ans in other questions)

[@rajkumarchaudhary3903]

where is Dp in this approach ??

[@sauravchaudhary3064]

GFG CODE FOR REFERNCE int solve(Node* root,int &res){ if(root==NULL ){ return 0; } int l=solve(root->left,res); int r=solve(root->right,res); int temp=1+max(l,r); int ans=max(temp,1+l+r); res=max(res,ans); return temp; } int diameter(Node* root) { // Your code here int res=INT_MIN; solve(root,res); return res; }

[@rohitdoyal8226]

Why we return temp ; in recursive function?

[@vinaysarilla4889]

Aditya Man....can you start series on Backtracking

[@kumarsaurabhraj2538]

The explanation could have been a little better.. Actually the function is returning the right of the tree and while finding the height of the tree for every node we are also considering the possibility that would would the diameter of the entire tree if the it passes through the node we are currently evaluating, we compare it with the diameters for nodes we have previously evaluated and store that if its greater. Finally after we have traversed the entire tree we end up with the diameter of the entire tree in our reference variable.

[@AkshayKumar-kz6zh]

this can be done w/o DP. First we need to traversal tree to find level of each leaf node. Second, select leaf at bottom most level(say X). Now using X as root traverse the tree keeping a counter variable(counter increments on each level). It will give answer.

[@kunalbabbar7399]

Yes, we can do without dp by pre order traversal on tree

[@prinzuchoudhury6920]

@@kunalbabbar7399 This, itself is preorder bro.

[@kunalbabbar7399]

@@prinzuchoudhury6920 yes

[@kunalbabbar7399]

@@prinzuchoudhury6920 but it's not looking like dp

[@prinzuchoudhury6920]

@@kunalbabbar7399 Dp is involved. Each recursive call of subtree is returning a answer to top part of tree,it means that we are building the tree from bottom to top and the answers computed at the bottom are passsed to the top, But it its not stored in seperate table since those temp and res are themselves getting updated in each call.

[@raghavsharma4837]

class Solution { public: int solve(TreeNode* root, int &res) { if(root == NULL) return 0; int l = solve(root -> left, res); int r = solve(root -> right, res); int temp = max(l , r) + 1; //int ans = max(temp, 1 + l + r); res = max(res, l + r); return temp; } int diameterOfBinaryTree(TreeNode* root) { int res = INT_MIN; solve(root, res); return res; } };

[@sagardas4569]

Sachme vaiya apke video dekhne k baad lagtai nahi dp ya recursion koi tough nahi he, lekin competive me halat thoda kharap ho jata he😢, uska kuch upai bolo na

[@JitendraKumar-ud5yc]

int height(Node *root) { if(root ==NULL) return 0; int lh=height(root->left); int rh=height(root->right); return 1+max(lh,rh); } int solve(Node* root,int &ans){ if(root ==NULL) return 0; int left=height(root->left); int right=height(root->right); ans=max(ans,left+right); solve(root->left,ans); solve(root->right,ans); return ans; } // Function to return the diameter of a Binary Tree. int diameter(Node* root) { // Your code here if(root==nullptr) return 0; int ans=0; return 1+solve(root,ans); }