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 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
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.
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))
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
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 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.
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.
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.
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)); } }
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?
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.
Sir there is a problem with this explanation.In case of an AVL tree where the diameter is supposed to be zero,this gives out some other ans.Kindly check on that!!
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).
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.
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)
doesnt work for me... any error in the code below... int height(TreeNode* root){ if(root == nullptr) return 0; int lheight = 1 + height(root->left); int rheight = 1 + height(root->right); return max(lheight, rheight); }
int diameterOfBinaryTree(TreeNode* root) { if(root == nullptr) return 0;
int lheight = height(root->left); int rheight = height(root->right); int ldiameter = diameterOfBinaryTree(root->left); int rdiameter = diameterOfBinaryTree(root->right); return max(lheight + rheight + 1, max(ldiameter, rdiameter)); }
//removing +1 worked.. can you tell me why?? have I implemented height of the tree wrong.. because removing 1 will actually deafeat the logic just explained in the video return max(lheight + rheight , max(ldiameter, rdiameter));
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; } }
C++ code class Solution { public: int diameterOfBinaryTree(TreeNode* root) { if (!root) return 0; int lheight = height(root->left); int rheight = height(root->right); int ldiameter = diameterOfBinaryTree(root->left); int rdiameter = diameterOfBinaryTree(root->right); return max((lheight + rheight), max(ldiameter, rdiameter)); } int height(TreeNode* root){ if (!root) return 0; int lheight = height(root->left); int rheight = height(root->right); if (lheight > rheight) return(lheight+1); return rheight+1; } };
@@agyatanonymous3995 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int diameterOfBinaryTree(TreeNode root) {
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 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
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.
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
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.
just wow! I was struggling so much and you made this crystal clear. Thankyou! Great video~!
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
Sir Your explanation is nice , every person can easily understand
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 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 .
You are blessed with teaching. I wish I had found this video earlier.
Vivek, that is a great video. Great explanation that is very much personalized for everyone. Thank you!
You Explain like a PRO..Thanks for such a detailed explanation!
Most thorough explanation out there! Great job!
Could you follow-up with how do solve Leetcode 1245: Tree Diameter, which is similar to this? Thanks for the great instructional videos.
Thank youu. I was really struggling to understand this and you explained it beautifully
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
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);
}
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)?
Could you please post code as well so that we can copy parts of it and test it out ourselves?
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
Really nice explanation keep up the good work buddy!
Thanks sir, I was just forgetting the 2nd case when diameter is not passing through the root. Not I got it. Thanks
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.
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));
}
}
Best Explaination so far. Thankyou sir
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
You're great! Hope u get many likes and subs.
your videos are amazing, you just need to put them in order so that it would be easier for the viewer.
Complexity is O(n^2) right?
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?
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?"
While calculating diameter , why are not doing +1 ?
if so will the diameter value get increment ?
You are an awesome teacher! Keep up the good work.
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.
Best explanation out there. Thanks Vivekanand.
can u please make a video on RED-BLACK Tree
what is the TIME COMPLEXITY for this?
O(n^2)
great explanation. Thank you vivekanand fo such a good video.
Beautifully explained :) Thank you.
Sir there is a problem with this explanation.In case of an AVL tree where the diameter is supposed to be zero,this gives out some other ans.Kindly check on that!!
this is the best explanation i was looking for u. thank u for making it so simple :)
What's the time and space complexity?
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).
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...
Thanks a lot! 😊
A very good explanation 👌
Perfect speed for me
In first example some people would say that diameter is 8 not 9.
how to find sum of nodes of a diameter
????
why you stopped to upload new videos
Any one plz tell that what i do when error is occur that "max" is not mainationed here
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
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
sir can u do a video on find the largest bst(binary search tree) in a binary tree .
Problem is very well explained ....gr8 Sir
What is the time complexity of this approach?
O (n^2)
NARASIMHA KARUMANCHI. THANKS FOR DETAIL EXPLANATION
doesnt work for me...
any error in the code below...
int height(TreeNode* root){
if(root == nullptr) return 0;
int lheight = 1 + height(root->left);
int rheight = 1 + height(root->right);
return max(lheight, rheight);
}
int diameterOfBinaryTree(TreeNode* root) {
if(root == nullptr) return 0;
int lheight = height(root->left);
int rheight = height(root->right);
int ldiameter = diameterOfBinaryTree(root->left);
int rdiameter = diameterOfBinaryTree(root->right);
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}
//removing +1 worked..
can you tell me why??
have I implemented height of the tree wrong..
because removing 1 will actually deafeat the logic just explained in the video
return max(lheight + rheight , max(ldiameter, rdiameter));
but it worked on gfg, not in leetcode
@@tonyriddle7646 Prolly because in your height function you already had + 1
thank you for explaining the concept of diameter of binary tree!
wow best explanation so far. Thank you!
This is brute Force . You need to go for optimal solution
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
Thank you Bhaiya. Doubt cleared. 😊
Please make more videos. Very helpful.
Why does recursion have to be so complex?
Khup Sunder Explain Kelat!!! Dhanyavad
I am very big fan of yours. Please keep up the good work.
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;
}
}
I only see this video and subscribed. Just EXCELLENT.
Very nice explanation sir.I really appreciate your efforts.Thanks.
Can you explain the O(n) solution?
SUPREME explanation. thanks!!
thanks for lucid explanation
amazing. thank you
Great video and great explanation. Thanks a lot!
perfect!!!!!!!! perfect explanation!!!!!!!!!!! Thanks :)
hello sir,
can you please add a video on hashing and hash tables
thankyou
Maybe we don’t need to add 1 after lheight + rheight?
it depends. The explanation of Depth and Height varies from book to book!
No we have to add 1
beautiful explanation
Great explanation
The definition of the diameter in this video is wrong. Should be Diameter = number of nodes on the longest path - 1
Great video!!!
Gist:
Max of ( Diameter passing through root, Max diameter not passing through root )
why did u stop making videos??? You are damn good man
yes
Superb explanation!
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
Well explained! Thank you for this!
your explanation is good but i think u should use stack also to run each steps
thank u 4 this video
C++ code
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int lheight = height(root->left);
int rheight = height(root->right);
int ldiameter = diameterOfBinaryTree(root->left);
int rdiameter = diameterOfBinaryTree(root->right);
return max((lheight + rheight), max(ldiameter, rdiameter));
}
int height(TreeNode* root){
if (!root) return 0;
int lheight = height(root->left);
int rheight = height(root->right);
if (lheight > rheight) return(lheight+1);
return rheight+1;
}
};
thanks bri im a iitian very beginnner in coding thanks
e(v)=8 ,i.e d(v,U1)=8 and d(v,U2)=8 then what is the relation between U1 and U2
Can u show the optimized code that takrs only O(n) time
Yes sure ...will make a video for the optimized code.
@@vivekanandkhyade Can we use Dynamic Programming to boost it up?
@@agyatanonymous3995
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if(root == null) return 0;
HashMap memoMap = new HashMap();
return diameterOfBinaryTree(root, memoMap);
}
public int diameterOfBinaryTree(TreeNode root, HashMap memoMap) {
if(root == null) return 0;
if(memoMap.containsKey(root)) return memoMap.get(root);
int leftHeight = height(root.left, memoMap);
int rightHeight = height(root.right, memoMap);
int leftDia = diameterOfBinaryTree(root.left, memoMap);
int rightDia = diameterOfBinaryTree(root.right, memoMap);
int res = Math.max(leftHeight+rightHeight, Math.max(leftDia, rightDia)) ;
memoMap.put(root,res);
return res;
}
public int height(TreeNode node, HashMap memoMap){
if(node == null) return 0;
int height = 1 + Math.max(height(node.left, memoMap),
height(node.right, memoMap));
return height;
}//end height
}//end dia
@@foo.1396
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int height(TreeNode* root, int &diameter){
if(!root)
return 0;
int l=height(root->left,diameter);
int r=height(root->right,diameter);
diameter=max(diameter,l+r+1);
return max(l,r)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
int diameter=0;
height(root,diameter);
return diameter;
}
};
nice explaination man keep posting .post some greedy method videos
Very nice explanation !
You are soooo gooooddd at this
Good explanation, thank you!
Excellent explanation
very well explained
Great explaination