Diameter of a binary tree | Leetcode

[@kharlopena7512]

Thank you so much! I've been looking up leetcode explanations and every time I find one from you it's ALWAYS the clearest and easiest to understand! YOU ROCK!

[@krishnakeshav23]

awesome ..so basically we need to return height of the tree in the same recursion as max(c1, c2, c3).

[@techdose4u]

👍🏼

[@shashanktiwari4442]

Sudden increase in difficulty lol

[@techdose4u]

😂

[@dinner4chiahao]

Thank you! Much better explanation than the other videos out there.

[@techdose4u]

Welcome :)

[@gopikumar7888]

//Approach 1 int height(Node *root){ if(root==NULL) return -1; return 1+max(height(root->left),height(root->right)); } Node *diameterTree(Node *root){ if(root==NULL) return; int option1=height(root->left)+height(root->right); int option2=diameter(root->left); int option3=diameter(root->right); return max(option1,max(option2,option3)); } //Approach 2 - Efficient Approach //in pair first ==Height, second==diameter pair DiameterHeightTree(Node *root){ if(root==NULL){ pairp; p.first=0; p.second=0; return p; } pairleftAns=DiameterHeightTree(root->left); pairrightAns=DiameterHeightTree(root->right); int leftDia=leftAns.second; int leftHeight=leftAns.first; int rightDia=rightAns.second; int rightHeight=rightAns.first; int height=1+max(leftHeight,rightHeight); int diameter=max((leftHeight+rightHeight),max(leftDia,rightDia)); pairp; p.first=height; p.second=diameter; return p; }

[@techdose4u]

👍

[@adhyayan2591]

The video put forward the algorithm in a complex way and I understood it. I just have a doubt. Can you please tell me, how you came to the conclusion on which method to use to solve this problem? I want to know how you approached this solution. (More elaborate - how did you think of this algorithm and what is the mathematical or logical approach to it). Thank you.

[@suyashmisra7406]

there is no single answer to your query. in fact, there is at least one more way to attack the problem(which is a very elegant approach but difficult to think of). what generally helps is to consider small test cases ,which often show you how you can approach the problem.using small examples, you can easily guess that in some trees,the diameter will pass through the root,so it's simply a matter of finding the max depth to the left and right of the root and andding them . however, for trees that don't have the root on the diameter, you have to be a little cleverer than that. a very basic way to circumvent this problem can be this : for every node, to store the length of "the diameter that passes through that node" . of course , there is lots of room for optimising this. after some optimisations and thinking, you may get to the optimal solution. i hope you'll find this useful.

[@adhyayan2591]

@@suyashmisra7406 Thank you I found it useful.

[@mwshubham]

Shortness of recursion code is amazing

[@techdose4u]

:)

[@siddharthmaurya6793]

@@techdose4u int dia(TreeNode* root,int &r) { int left ,right; if(!root){ return 0; } left= dia(root->left,r); right=dia(root->right,r); r=max(r,left+right+1); return max(left,right)+1; } int diameterOfBinaryTree(TreeNode* root) { int r=-1; dia(root,r); return r-1; } better solutin than yours.....

[@Rahul-rp5hk]

Find depth of tree using recursion and add depth of left + right subtree and update it to max

[@techdose4u]

Actually the concept is simple. I made it look complex 😅

[@pritamsarkar3371]

😂😂😂 omg its crazy

[@akankshagoyal2508]

best channel ever

[@techdose4u]

❤️

[@DreaMagnifier]

If we take a global max variable,update it by summing the lhs and rhs path , at each point ,will we get answer.

[@crimsoncad3230]

It was the toughest problem till now in the April Challenge.

[@ryan-bo2xi]

its not tough when you understand. First find height of both left and right side and add . Next find diameter of left side and diameter of right side. Max(left+right,diameter left,diameter right) www.geeksforgeeks.org/diameter-of-a-binary-tree/

[@Apoorvpandey]

What does the pair means? (0,0) for leaf node what is 0,0

[@sleepypanda7172]

Thanks a lot. Literally mean it, pal.

[@techdose4u]

Welcome

[@kunalsoni7681]

I understand this problem 😇.. and explanations is brilliant thank you sir

[@techdose4u]

Welcome :)

[@najimali32]

didn't understand your explanation. I have written a simpler approach & code. Approach - apply post-order traversal & count the no of nodes from both side & our output will be the max of left + right node. class Solution { static int max; // global variable public int diameterOfBinaryTree(TreeNode root) { max =0; int a = diaUtil(root); return max; } static int diaUtil(TreeNode node){ if (node==null){ return 0; } int l = diaUtil(node.left); int r = diaUtil(node.right); max = Math.max(max,l+r); return 1+Math.max(l,r); } }

[@techdose4u]

Thanks for sharing :)

[@ryan-bo2xi]

What is the variable a ? int a = diaUtil(root); Its confusing . What if my tree has the longest path only on left subtree or right subtree .

[@yaswanthalapati8264]

@@ryan-bo2xi that's y we used Math.max(max,l+r) If theres a max distance in left or right subtree then it will already be stored there before u reach the root node ..

[@prasadarepalli7449]

In example case 2. You have mentioned diameter of tree 10. How that can be? No of nodes are 10 so Diameter would be 9 right ? (nodes = edges + 1)

[@techdose4u]

Correct. It should be 9 in terms of edges and 10 in terms of nodes. Question is to find in terms of edges. So 9 is correct.

[@anojk1]

Excellent explanation with the good example

[@techdose4u]

Thanks :)

[@maruthkamath9304]

I think this video needs an edit at 6:15, its not max(0,0)+1 for the third case , instead it is 0+0+1.Can we have that corrected please?

[@vishaljat3314]

just tell me weather it is o(n) approach or not int go(Node* n, int* dia) { if (!n) return 0; int l = go(n->left, dia); // height of left subtree int r = go(n->right, dia); // height of right subtree if (l + r + 1 > *dia) *dia = l + r + 1; // l+r+1 is a possible max dia return 1 + max(l, r); // returning height of subtree } int diameter(Node* node) { int dia = 0; go(node, &dia); return dia; }

[@paragroy5359]

Nice explanation sir...... is it possible that the iterative solution of this problem is asked in interview or this recursive approach is ok..

[@techdose4u]

Anything is okay as long as you explain a solution.

[@vishalimanivannan7109]

Hi Tech dose, you have done a pretty decent job :) thanks for your efforts. I think case 2 covers all the cases and case 1 isn't necessary. Please correct me if I'm wrong.

[@techdose4u]

Maybe you are correct. Verify it by just submitting your code. I have unnecessarily made the explanation longer. You can watch my other tree videos as well.

[@vishalimanivannan7109]

@@techdose4u not really. Coming up with solution is one thing, explaining the same to others is a whole different deal. Your other videos have been helpful. Thanks.

[@vishalimanivannan7109]

I did verify my code and case 1 seems redundant. Thank you

[@MGtvMusic]

@@vishalimanivannan7109 Yes same

[@shubhankarbhadra131]

superb explanation man! Your way of teaching is cool and easy to grasp also! Thanks for your efforts.

[@techdose4u]

Some did not understand. I am happy that some did 😅

[@soumensinha305]

Its tough question as compared to previous question

[@techdose4u]

The concept is simple. I made it look complex in the video 😅 but the cases are correct.

[@piyushlohiya1977]

Isn't first solution wrong because just calculating max height will never give the correct answer right?

[@danielbartolini115]

can someone please explain what is the space complexity adn why

[@palakgupta4104]

what are the time and space complexity for this??

[@roshanbhattad4493]

thank you brother

[@techdose4u]

Welcome

[@debaratighatak2211]

your videos are always really helpful,thank you for the brilliant explanation! 😇

[@cloud15487]

That question is marked with easy @all.

[@techdose4u]

Should have been medium though

[@cloud15487]

@@techdose4u yup

[@apoorvgarg0204]

Beautiful Explanation !

[@techdose4u]

Thanks :)

[@liingpangryantee7203]

1:50 I believe the diameter of Case 2 should be 9?

[@aakashyadav6228]

Yes

[@pahehepaa4182]

Wish you could explain a little better for the beginners.

[@techdose4u]

I went too far and explained in too detailed manner than I should have. I realized it. I am trying to improve by every video. Hope you will understand other lectures :)

[@ramanshusingh7516]

Your code doesnt work on gfg bro

[@perisetlasatwik8139]

abe thumbnail pe leetcode ke logo change karlo PHUB ka logo hai vo 😂😂😂

[@kaushaljalan2928]

Explanation wasn't good

[@techdose4u]

It was complex. Should have explained in an easier way.

[@sase1017]

Your explanation covers too much of repeated rambling words for same logic example, instead of focus on give clear overall picture, It just causes confusion, I m sure many people feel the same way that this questions can be shorten in 5 mins give people clear understanding

[@techdose4u]

This question is much easier than how I explained. This is one video which I did not explain well. Try other videos and I hope you will not be disappointed.

[@sase1017]

@@techdose4u Thank you for your hard work!

[@NoorAli-uh4uq]

@TECH DOSE you are doing great job.

[@deveshkumar8823]

Don't waste your time watching this ...it's too complex

[@techdose4u]

I think this could have been made much easier 😅

[@acro0008]

explaination is not so good

[@techdose4u]

Yes true. This is one video where I messed up 😅