Diameter of a Binary Tree (Code/ Algorithm)
Вставка
- Опубліковано 19 вер 2024
- Find the diameter of a binary tree. The number of nodes on the longest path in a binary tree is the diameter. This is a recursive code.
Height of a binary Tree video :- • Height of a Binary Tre...
This is a great video, perfect speed for someone new and with English second language. Thank you for making it so easy to understand!
Totally Agree.He is so real explanation ,no hussle and .He is so real!!
True
your way of slow explanation is very effective and efficient as these recursive problems are understood best when someone explains slowly other wise its difficult to keep track of recursive call flows, so keep going the way you are and keeping sharing knowledge like you are doing now.
I appreciate your solution, it was the only one I could understand on this topic. FYI, I translated this to JavaScript. However, for the final result portion, I removed '+1' from the height equation in the diameter function because the height function already includes a +1 to the left or right tree. It passed all cases when I did that.
Probably, you solved on leet code, where is not nodes but the most number of edges. which are 1 less than the number of nodes.
I watched 10s of videos which is explaining the same problem, your video is the only one that made me finally get it, You're an awesome teacher, keep going
Sir you have perfect explanation for every problem.....you can write your own book....you explain better than best books out there of data structures
just wow! I was struggling so much and you made this crystal clear. Thankyou! Great video~!
Very good explanation! The other guys were confusing until I stumbled upon this guy's video.
Just play this video 1.5 speed.
2x works as just perfectly!
LOL ! But, he is a great teacher and doing awesome job ! Thank you !
I wish there is 3X option.
@@ishan_kumar press ctrl + shift + j. In the console window type
document.getElementsByTagName("video")[0].playbackRate = 3.0
@@ishan_kumar U can also add video speed controller extension
Just one correction or making everyone aware. when calculating the height of the tree, you should include the root too. hence in the diameter math you can simply do
return Math.max(leftHeight+rightHeight , Math.max(lDiameter, rDiameter))
True, with the video from the same problem description for the height would be confusing.
Sir Your explanation is nice , every person can easily understand
Most thorough explanation out there! Great job!
correct solution , other than the fact is maximum diameter could be number of edges in the path , not the number of nodes, in that case we don't have to add extra 1 to the heights
Implementation in JS..it works! Thank you sir.
function binaryTreeDiameter(tree) {
// Write your code here.
if (!tree) return 0;
const heightOfLeft = height(tree.left);
const heightOfRight = height(tree.right);
const heightOfNode = 1 + Math.max(heightOfLeft, heightOfRight);
const diameterLeft = binaryTreeDiameter(tree.left);
const diameterRight = binaryTreeDiameter(tree.right);
const pathThroughRoot = heightOfRight + heightOfLeft;
const maxDiameterBelow = Math.max(diameterLeft, diameterRight);
return Math.max(maxDiameterBelow, pathThroughRoot);
}
function height(tree) {
if (!tree) return 0;
const left = height(tree.left);
const right = height(tree.right);
return 1 + Math.max(left, right);
}
Vivek, that is a great video. Great explanation that is very much personalized for everyone. Thank you!
You are blessed with teaching. I wish I had found this video earlier.
Thanks sir, I was just forgetting the 2nd case when diameter is not passing through the root. Not I got it. Thanks
you make things so simple bro. thank you for sharing. I am fan of you. could you please sometime post video on eigen value and eigen vectors
Is I am the only one who give reply of his hello when in good mood :) hahaha lol
lol i said okay every time he said "okay?"
You Explain like a PRO..Thanks for such a detailed explanation!
Great explanation, loved it. But I just want to make a point that this is not the most efficient solution. For a given node, we are calculating the height and the diameter separately when you can get the diameter while calculating the height.
that is true , height can be calculated while calculating the diameter by just adding one more parameter .
I am a very big fan of you bro.. plz make more videos.. and my humble request to you is that it will very much helpful if you consider some java while explain the code... Thanks from coimbatore.
great explanation. Thank you vivekanand fo such a good video.
Problem is very well explained ....gr8 Sir
Good video. You can get a O(n) time algorithm by getting the diameter and height in the same recursive call. Just pass by reference the height in the diameter function.
can you please show how to do this? i couldn't figure it out myself...
You are an awesome teacher! Keep up the good work.
finding a recursive solution is extremely tough ):
I kinda like how creative your username is😂... Made my day😂😂
Hmm it is difficult to find recursive one
Thank youu. I was really struggling to understand this and you explained it beautifully
You're great! Hope u get many likes and subs.
perfect!!!!!!!! perfect explanation!!!!!!!!!!! Thanks :)
Beautifully explained :) Thank you.
Really nice explanation keep up the good work buddy!
Best Explaination so far. Thankyou sir
your videos are amazing, you just need to put them in order so that it would be easier for the viewer.
Could you follow-up with how do solve Leetcode 1245: Tree Diameter, which is similar to this? Thanks for the great instructional videos.
One thing to note here is the repeated calculation of height is inefficient. So if you're coding it out, you should return a pair "height+diameter" for every subtree. But I understand that Vivekanand (OP, instructor) here omitted it because it distracts us from the main goal of finding the diameter here.
Great video!!!
Thanks a lot! 😊
A very good explanation 👌
Perfect speed for me
thanks for lucid explanation
Khup Sunder Explain Kelat!!! Dhanyavad
Can you make a video on "Maximum sum of nodes in Binary tree such that no two are adjacent" I am not able to understand this question and it was asked in the interview of my senior. So please sir a humble request from you from a subscriber please make a video on this question. It will be really helpful for students like us. Thank you for teaching...Your videos are super awsome.
beautiful explanation
Best explanation out there. Thanks Vivekanand.
thank you for explaining the concept of diameter of binary tree!
NARASIMHA KARUMANCHI. THANKS FOR DETAIL EXPLANATION
Great explanation
Diameter of a tree can be calculated by only using the height function, because the diameter of a tree is nothing but maximum value of (left_height + right_height + 1) for each node. So we need to calculate this value (left_height + right_height + 1) for each node and update the result. Time complexity - O(n)
could u please show how to do this? i couldn't figure this out myself
SUPREME explanation. thanks!!
The explanation is really clear, but I have a doubt about the time complexity of this solution, it would be O(n²) or O(n)?
Very nice explanation sir.I really appreciate your efforts.Thanks.
this is the best explanation i was looking for u. thank u for making it so simple :)
Great explaination
The time complexity of this algo is O(N^2) right? Because we have to calculate the height as well as the diameter for each given node, and for both we need to make recursive calls down the tree.
Also, where is the height function here? I was looking for the same comment
Thank you Bhaiya. Doubt cleared. 😊
Please make more videos. Very helpful.
I only see this video and subscribed. Just EXCELLENT.
I am very big fan of yours. Please keep up the good work.
Great video and great explanation. Thanks a lot!
This code doesn't seem to work unless you write it like this. You adjust the return statements to -1 and +2
class Solution {
public int height(TreeNode root)
{
if(root==null)
return -1;
else{
int left = height(root.left);
int right = height(root.right);
return Math.max(left,right)+1;
}
}
public int diameterOfBinaryTree(TreeNode root) {
// base case if tree is empty
if (root == null)
return 0;
// get the height of left and right sub-trees
int lh = height(root.left);
int rh = height(root.right);
// get the diameter of left and right sub-trees
int ld = diameterOfBinaryTree(root.left);
int rd = diameterOfBinaryTree(root.right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1
*/
return Math.max(lh + rh + 2,
Math.max(ld, rd));
}
}
very well explained
wow best explanation so far. Thank you!
Very nice explanation !
Superb explanation!
Well explained! Thank you for this!
This is brute Force . You need to go for optimal solution
Excellent explanation
good tutorial but this is O(n-square) solution. O(n) solution can be obtained by using height function. Code below:
class Tree
{
/* Complete the function to get diameter of a binary tree */
int diameter(Node root)
{
Res r = new Res();
diameter(root,r);
return r.val;
}
int diameter(Node root, Res res)
{
if(root==null) return 0;
int lh = diameter(root.left,res);
int rh = diameter(root.right,res);
res.val = Math.max(res.val, lh+rh+1);
return Math.max(lh,rh)+1;
}
}
Very good! Thank you sir.
You are soooo gooooddd at this
Just one word "Awesome" :)
your explanation is good but i think u should use stack also to run each steps
thank u 4 this video
great explanation!
Good explanation, thank you!
YOU ARE A HERO!!!!!!!
nice explaination man keep posting .post some greedy method videos
In first example some people would say that diameter is 8 not 9.
Good Explanation.
Great work !
Dear Professor,
Please can you make a video on how to find the maximum width of a binary tree.
Thank You
level order traversal might be the answer for this
Can someone please help me understand the concept of length of the path. I mean in this problem what sir is explaining is it assumed that length of path = number of nodes on the path OR is length of path = is represented by the number of edges between them? since this could change the way we implement right?anyone?
Thanks for the video. Also, try to explain the time complexity of the solution.
this is a O(N^2) solution, i would only study O(N) solutions
Thanks a lot for making us understand
sir, in the very first tree, lheight will b 2 n rheight=4 then lheight+right+1= 7 whereas answer should be 9 ...I am confused .pls explain
lHeight = 3 and rHeight = 5.
lHeight + rHeight + 1 = 3 + 5 + 1 = 9
Height of a tree = number of edges between the root and the farthest leaf
amazing. thank you
why did u stop making videos??? You are damn good man
yes
Could you please post code as well so that we can copy parts of it and test it out ourselves?
what is the TIME COMPLEXITY for this?
O(n^2)
this was awesome! thank you!
While calculating diameter , why are not doing +1 ?
if so will the diameter value get increment ?
can u please make a video on RED-BLACK Tree
Gist:
Max of ( Diameter passing through root, Max diameter not passing through root )
You are really great!
thank you for the explanation
Very clear, thanks
Best vedio
The definition of the diameter in this video is wrong. Should be Diameter = number of nodes on the longest path - 1
What's the time complexity of your proposed solution? Looks like quite hard to analyze.
Time complexity is O(2n) i.e O(n) where n is the number of nodes in the tree. In all the recursive calls, you find the height of left and right subtree by visiting each node at most once. Then you find the diameter of left subtree and right subtree considering root as any node in tree except the root of original tree, and this makes you visit n nodes again. Therefore, 2n which is none other than O(n).
He is god of algorithms....❤️❤️
Excellent !
very helpful! Thanks
Complexity is O(n^2) right?