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!
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/
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.
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.
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); } }
@@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 ..
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.
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.
@@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.
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; }
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 :)
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
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.
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!
Sudden increase in difficulty lol
😂
awesome ..so basically we need to return height of the tree in the same recursion as max(c1, c2, c3).
👍🏼
Thank you! Much better explanation than the other videos out there.
Welcome :)
//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;
}
👍
Shortness of recursion code is amazing
:)
@@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.....
Find depth of tree using recursion and add depth of left + right subtree and update it to max
Actually the concept is simple. I made it look complex 😅
😂😂😂 omg its crazy
It was the toughest problem till now in the April Challenge.
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/
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.
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.
@@suyashmisra7406 Thank you I found it useful.
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);
}
}
Thanks for sharing :)
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 .
@@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 ..
best channel ever
❤️
If we take a global max variable,update it by summing the lhs and rhs path , at each point ,will we get answer.
Thanks a lot. Literally mean it, pal.
Welcome
Excellent explanation with the good example
Thanks :)
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.
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.
@@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.
I did verify my code and case 1 seems redundant. Thank you
@@vishalimanivannan7109 Yes same
What does the pair means? (0,0) for leaf node what is 0,0
Nice explanation sir...... is it possible that the iterative solution of this problem is asked in interview or this recursive approach is ok..
Anything is okay as long as you explain a solution.
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)
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.
superb explanation man! Your way of teaching is cool and easy to grasp also! Thanks for your efforts.
Some did not understand. I am happy that some did 😅
I understand this problem 😇.. and explanations is brilliant thank you sir
Welcome :)
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?
Its tough question as compared to previous question
The concept is simple. I made it look complex in the video 😅 but the cases are correct.
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;
}
your videos are always really helpful,thank you for the brilliant explanation! 😇
Isn't first solution wrong because just calculating max height will never give the correct answer right?
thank you brother
Welcome
Beautiful Explanation !
Thanks :)
Wish you could explain a little better for the beginners.
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 :)
That question is marked with easy @all.
Should have been medium though
@@techdose4u yup
can someone please explain what is the space complexity adn why
Don't waste your time watching this ...it's too complex
I think this could have been made much easier 😅
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
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.
@@techdose4u Thank you for your hard work!
@TECH DOSE you are doing great job.
Explanation wasn't good
It was complex. Should have explained in an easier way.
what are the time and space complexity for this??
abe thumbnail pe leetcode ke logo change karlo PHUB ka logo hai vo 😂😂😂
1:50 I believe the diameter of Case 2 should be 9?
Yes
Your code doesnt work on gfg bro
explaination is not so good
Yes true. This is one video where I messed up 😅