Diameter of a Binary Tree (Code/ Algorithm)

[@irynasherepot9882]

This is a great video, perfect speed for someone new and with English second language. Thank you for making it so easy to understand!

[@unboxingzindagi9972]

Totally Agree.He is so real explanation ,no hussle and .He is so real!!

[@tsupreetsingh]

True

[@opeyemijonah9480]

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.

[@User-nq9ee]

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.

[@praveenchouhan6388]

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.

[@TheSridharraj]

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))

[@kulaudo]

True, with the video from the same problem description for the height would be confusing.

[@Adityasharma-oe8zp]

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

[@mareimorsy3182]

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

[@ABU_BEKIR_SIDDIK]

Just play this video 1.5 speed.

[@agyatanonymous3995]

2x works as just perfectly!

[@humblecoder9119]

LOL ! But, he is a great teacher and doing awesome job ! Thank you !

[@ishan_kumar]

I wish there is 3X option.

[@sandeepvedavyas8701]

@@ishan_kumar press ctrl + shift + j. In the console window type document.getElementsByTagName("video")[0].playbackRate = 3.0

[@kartikaygoel3042]

@@ishan_kumar U can also add video speed controller extension

[@pahehepaa4182]

Very good explanation! The other guys were confusing until I stumbled upon this guy's video.

[@staffeng]

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.

[@aruneshsrivastava7154]

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

[@griffinbaker9792]

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); }

[@AbhiKumar-yk9sr]

Sir Your explanation is nice , every person can easily understand

[@ytuser659]

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.

[@kasyapdharanikota8570]

that is true , height can be calculated while calculating the diameter by just adding one more parameter .

[@jeezradz]

just wow! I was struggling so much and you made this crystal clear. Thankyou! Great video~!

[@opeyemijonah8530]

You are blessed with teaching. I wish I had found this video earlier.

[@ChandraShekhar-by3cd]

You Explain like a PRO..Thanks for such a detailed explanation!

[@jacktrainer4387]

Most thorough explanation out there! Great job!

[@pauldaviddavies]

Vivek, that is a great video. Great explanation that is very much personalized for everyone. Thank you!

[@jhanvibatra828]

Best Explaination so far. Thankyou sir

[@elebs_d]

Thank youu. I was really struggling to understand this and you explained it beautifully

[@thelasttimeitookashowerwas7069]

finding a recursive solution is extremely tough ):

[@nivedithat4745]

I kinda like how creative your username is😂... Made my day😂😂

[@jatin1688]

Hmm it is difficult to find recursive one

[@K_EC_AushoRoup]

Thanks sir, I was just forgetting the 2nd case when diameter is not passing through the root. Not I got it. Thanks

[@saurabhsen3560]

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.

[@preetisaroha3118]

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)

[@JJ-Bond]

could u please show how to do this? i couldn't figure this out myself

[@anig3465]

NARASIMHA KARUMANCHI. THANKS FOR DETAIL EXPLANATION

[@prateekkanujiya9775]

This is brute Force . You need to go for optimal solution

[@User-nq9ee]

Beautifully explained :) Thank you.

[@DismalDante]

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.

[@JJ-Bond]

can you please show how to do this? i couldn't figure it out myself...

[@shreyasangane3822]

Khup Sunder Explain Kelat!!! Dhanyavad

[@rsKayiira]

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)); } }

[@kmlx19]

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)?

[@vadirajjahagirdar2615]

Best explanation out there. Thanks Vivekanand.

[@ghostpieces2362]

Could you follow-up with how do solve Leetcode 1245: Tree Diameter, which is similar to this? Thanks for the great instructional videos.

[@user-zj9pq5xc7x]

amazing. thank you

[@abhisekmandal1591]

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; } }

[@rakeshroshan829]

great explanation. Thank you vivekanand fo such a good video.

[@kushagrashekhawat8227]

You are an awesome teacher! Keep up the good work.

[@yvanpearson7024]

In first example some people would say that diameter is 8 not 9.

[@GAURAVKR1986]

Really nice explanation keep up the good work buddy!

[@learntogether-growtogether865]

Problem is very well explained ....gr8 Sir

[@dhruvilprajapati4734]

thanks for lucid explanation

[@vcfirefox]

SUPREME explanation. thanks!!

[@karansachdeva8516]

Great explanation

[@biswaMastAadmi]

beautiful explanation

[@hiteshdayaramani388]

thank you for explaining the concept of diameter of binary tree!

[@annieonee]

wow best explanation so far. Thank you!

[@mohdanaskhan7203]

your videos are amazing, you just need to put them in order so that it would be easier for the viewer.

[@dharanyuvi6951]

Gist: Max of ( Diameter passing through root, Max diameter not passing through root )

[@shashwatagrawal8412]

Thank you Bhaiya. Doubt cleared. 😊 Please make more videos. Very helpful.

[@preetisaroha3118]

Very nice explanation sir.I really appreciate your efforts.Thanks.

[@prashantnagrurkar2784]

Thanks a lot! 😊 A very good explanation 👌 Perfect speed for me

[@mchandresh]

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

[@vicky888]

Great video!!!

[@saivigneshrajendran867]

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.

[@pratapkumarchandra6488]

this is the best explanation i was looking for u. thank u for making it so simple :)

[@darod6098]

I only see this video and subscribed. Just EXCELLENT.

[@chetanjain5097]

Could you please post code as well so that we can copy parts of it and test it out ourselves?

[@parthshah6343]

Superb explanation!

[@griffinbaker9792]

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.

[@pranavbhat92]

Also, where is the height function here? I was looking for the same comment

[@abhisheka2p2]

You're great! Hope u get many likes and subs.

[@alfredoluco189]

Great video and great explanation. Thanks a lot!

[@DeviDevi-yr2sv]

Great explaination

[@rakeshroshan829]

can u please make a video on RED-BLACK Tree

[@TheSridharraj]

Complexity is O(n^2) right?

[@abhishekjain7173]

Very nice explanation !

[@kasyapdharanikota8570]

very well explained

[@Amanyadav-ec3hn]

Thanks for the video. Also, try to explain the time complexity of the solution.

[@yanlingyang256]

perfect!!!!!!!! perfect explanation!!!!!!!!!!! Thanks :)

[@RiteshSingh-op3jd]

I am very big fan of yours. Please keep up the good work.

[@yvanpearson7024]

this is a O(N^2) solution, i would only study O(N) solutions

[@georgebrooking3820]

YOU ARE A HERO!!!!!!!

[@ShivangiSingh-wc3gk]

Dear Professor, Please can you make a video on how to find the maximum width of a binary tree. Thank You

[@agyatanonymous3995]

level order traversal might be the answer for this

[@alishagarg150]

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!!

[@Adityasharma-oe8zp]

He is god of algorithms....❤️❤️

[@coderajput1816]

your explanation is good but i think u should use stack also to run each steps thank u 4 this video

[@a7medk7alid7]

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; } };

[@reviewsonly4894]

thanks bri im a iitian very beginnner in coding thanks

[@azad1300]

While calculating diameter , why are not doing +1 ? if so will the diameter value get increment ?

[@remyb9937]

Excellent explanation

[@animemaker7433]

why did u stop making videos??? You are damn good man

[@sivaganesh4489]

yes

[@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; }

[@johngerassimou8898]

Very good! Thank you sir.

[@tonyz2203]

Good explanation, thank you!

[@anamikaahmed4887]

Well explained! Thank you for this!

[@jegatheeshm93]

Good Explanation.

[@one_percent_up]

Just to the understading way to the concepts

[@veerrajuyeleti8541]

sir can u do a video on find the largest bst(binary search tree) in a binary tree .

[@jeezradz]

what is the TIME COMPLEXITY for this?

[@TheBreyHD]

O(n^2)

[@TianmenDream]

What's the time complexity of your proposed solution? Looks like quite hard to analyze.

[@bonkers4490]

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).

[@GauravKawatrakir]

This solution takes O(n2) "n square".

[@retrogame3138]

why you stopped to upload new videos

[@shrad6611]

Is I am the only one who give reply of his hello when in good mood :) hahaha lol

[@sameedyousuf6036]

lol i said okay every time he said "okay?"

[@goldent4655]

What's the time and space complexity?

[@niharikapatil902]

You are soooo gooooddd at this

[@dileepmatha8076]

how to find sum of nodes of a diameter ????

[@Atpugtihsrah]

Can you explain the O(n) solution?

[@piyushchaudhari397]

Great work !

[@PradeepKumar-so5wq]

nice explaination man keep posting .post some greedy method videos

[@MrAvtar1]

What is the time complexity of this approach?

[@Ashish.Shukla9]

O (n^2)

[@piotropyd9806]

great explanation !

[@basavarajpatil9821]

code for O(n) time complexity