L16. Diameter of Binary Tree | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@democratcobra]

Likeeeeeeeeed , Shareeeeed and subscribeeeeeed......Hope you are doing extremely well.

[@letmeinthefiend8522]

sir jav root pr phuche.. to maxL=1 and maxR=4 .. to root ki height hogi 4+1 ( jab code re return kia ). or maxi hohyi (4,4+1) .. to sir answer to 5 ana chaiy na... maxi 6 kaise aarhi h

[@reshmamaurya3601]

class Solution { public: int maxi = 0 ; int diameterOfBinaryTree(TreeNode* root) { if(root == NULL) return 0; int lh = height(root->left); int rh = height(root->right); maxi = max(maxi , lh+rh); return maxi; } int height(TreeNode* root){ if(root == NULL){ return 0 ; } int lh = height(root->left); int rh = height(root->right); return 1+max(lh , rh); } }; why is this code giving error ? Sir please help to find out the error i.e. I had implemented it using O(N^2) T.C. wala logic(the initial logic).

[@shubhamkumar1305]

​@@letmeinthefiend8522 Answer is 6. But gives 5 there will be change in some code.

[@shubhamkumar1305]

@@letmeinthefiend8522 Code:- if not root: return 0,maxi lh,maxi = diameterBt(root.left,maxi) rh,maxi = diameterBt(root.right,maxi) maxi = max(maxi,lh+rh) # print("maxi: ",maxi) return 1 + max(lh,rh),maxi x,diameter = diameterBt(root,maxi) print(diameter) # This will give you right answer.

[@VishalGupta-xw2rp]

The second last line in both the codes... diameter = max(diameter, lh+rh+1); +1 because Yes we have got the lh and rh of that node but we need to include that node itself also. Then only a whole path will be made. This video is just so nicely explained. ♥️

[@VishalGupta-xw2rp]

In the last line where +1 is written in both the codes.... There we are returning the height of that node itself. Like for leaf node lh=0, rh=0 but that +1 is doing all the magic.

[@mahaprasadm9770]

@@VishalGupta-xw2rp I understand where you're coming from but one important piece of information you may have missed is that the path does not necessarily have to pass through the root node. So in that case, we don't need the +1.

[@mr.twinklesharma5826]

That depends on question, Somewhere they consider the number of nodes in the longest path as diameter; on the other hand, the diameter is considered as the length of longest path which is nothing but the number of edges in the path and eventually one less than the number of nodes in the path. Ref: Leetcode & Geeksforgeeks

[@shubhamkumar1305]

If you written code in python, Code which I have written:- if not root: return 0,maxi lh,maxi = diameterBt(root.left,maxi) rh,maxi = diameterBt(root.right,maxi) maxi = max(maxi,lh+rh) return 1 + max(lh,rh),max depth, diameter = diameterBt(bt5,0) print(diameter) # Yu give maxi value of diameter.

[@SydMohan]

Logic fails if the +1 is missed .... thanks @VishalGupta good catch!

[@Abhishek-do8mp]

This could get tricky if you think clearly, actually the recursive function is returning the height for nodes not for branches we are just using it when we are trying to make answer for root which has been generated by it's child in terms of nodes not the branches.

[@studyaccount794]

Note to self- For all the right nodes the traversal will occur in similar fashion, i.e. first right then left again, so instead of jumping directly from 6 to 7 we'll check left of 6 first then go for it's right, i.e. 7. Striver skipped that because it's self explanatory.

[@dipeshsaili4468]

lol

[@tilakpatidar6092]

Its a very nice series, i already know about binary tree but i just see this video for get intuition for diameter of tree because all other youtubers use pointer to solve this question and i can't understand how pointer works, but after seeing this video i got a easy solution without any pointer and solve only mechanism of finding height of a tree nice series sir👍🏻

[@atjhamit]

Dude, if your language of choice is c / c++ make sure you get your pointer basics covered. Nothing justifies escaping it.

[@pathikritsyam3687]

@@atjhamit True.

[@kaushik.aryan04]

learn java

[@atjhamit]

@@kaushik.aryan04 It would be easier to learn pointers, I suppose :'

[@charlesbabbage6786]

Beautifully explained!!! Love the tracing.

[@rakshayadav1892]

Python code: class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: self.mx=0 self.helper(root) return self.mx def helper(self,root): if not root: return 0 l=self.helper(root.left) r=self.helper(root.right) self.mx=max(self.mx,l+r) return 1+max(l,r)

[@helloworld4788]

GOAT of leetcode, thanks brother.

[@chandantaneja6388]

Theeeee Best explanation. I was thinking of really difficult approach by making a pair class and return both max and height. But you gave the BEST solution i ever found.

[@paramsratanpal6551]

same

[@btOOVipulJarial]

coding ninjas? That course is shit

[@farhadpagdiwala1789]

That was a good explanation Striver. I'll watch this video one more time as I did not get the concept of why height is needed to compute the diameter.

[@pranav288]

we are adding heights thats why

[@JohnWickea]

ah man ! go back to basics . watch video again

[@anonymousvoid6356]

This is the best explanation on the internet ! This guy is a legend.

[@WithRVR]

can use `class variable` ...... like `max_diameter` then return it some thing like this ``` class Solution { int max_diameter = 0; public int diameterOfBinaryTree(TreeNode root) { maxDepth(root); return max_diameter; } private int maxDepth(TreeNode root) { if (root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); max_diameter = Math.max(max_diameter, left + right); return 1 + Math.max(left, right); } } ```

[@parth_3856]

//we have to add 1 to "mx=max(mx,l+r)" so it will become " mx=max(mx,l+r+1)"because the node it self also have to be included. full code-> int traversal(Node* root,int h,int l,int r,int &mx){ if(root==NULL) return 0; l=traversal(root->left,h,l,r,mx); r=traversal(root->right,h,l,r,mx); mx=max(mx,l+r+1); h=max(l,r)+1; return h; } int diameter(Node* root) { int mx=0; traversal(root,0,0,0,mx); return mx; } };

[@hustler516]

I was not able to do that question myself because i was missing a point that its not necessary that we need not to pass from the root........but after seeing this video all my doubt cleared ......Thanku bhyia

[@prajnyasushreesangita9729]

So far thr Best solution for diameter of binary tree..... In one program diameter and maxheight.... Both are done.. 👏👏👏👏👏...........

[@raj-nq8ke]

Then u must have not seen any other video

[@tusharkuchchal2891]

python solution class Solution: def __init__(self): self.maxi=0 def diameter(self,root): self.height(root) return self.maxi def height(self,root): if root==None: return 0 lh=self.height(root.left) rh=self.height(root.right) self.maxi=max(self.maxi,lh+rh+1) return 1+max(lh,rh)

[@adamyasharma_0135]

one of the best approach on this question.

[@abhishekusrathe6243]

Your tree series is amazing .having fun while watching it .keep it up bhiya .

[@musicmelodies8313]

U are amazing . I did it myself without even looking at pseudo code. Hats off man.

[@jayadubey_22]

on doing the dry run on my own getting more clarity thanks again 🙌

[@devanshdalwadi6015]

we does not need max(maxi,lh+rh+1) in diametere?

[@unknown47896]

​@@devanshdalwadi6015yes it's a mistake made by striver in the brute force approach

[@gandhijainamgunvantkumar6783]

Amazing explanation. I think there is slight mistake in the code. We have to take diameter = max(diameter, lh + rh+1). here we have to do +1 because we also have to count the node along with lh and rh. because The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes.

[@sushantsharma7051]

exactly bro, I was wondering the same

[@vanquishersgaming138]

It counts the length of path, NOT the number of nodes. So, +1 not needed...

[@vanquishersgaming138]

@@sushantsharma7051 I got what you saying. But the LeetCode question he was solving was counting the length between nodes. If you wanna count no of nodes (which is actually the diameter of tree) you can do +1, no issue.

[@preetampati6140]

That depends whether height is 0 indexed or 1 indexed.

[@chandantaneja6388]

@@preetampati6140 exactly just see the question requirement. like in gfg its doing +1 because ts counting the current node. But when they are not counting the current node its just slight changes. I guess you can seeby running some test cases and adjust the factor 1.

[@himangshudas6244]

Watched many videos for this question but this seemed to be the most comprehendible.

[@rafaelmarcos9733]

Now I understand the solution, thank you very much!

[@neerajkumarmarupalli5313]

Python Code: # O(n) time complexity # find heights of left and right sub trees and then update the value of answer def diameter(root,ans=[]): if root is None: return 0, ans lefth,leftans = diameter(root.left,ans) righth,rightans = diameter(root.right,ans) ans.append(lefth+righth) return 1+max(lefth,righth),ans height, diameters = diameter(root) print(max(diameters))

[@PrinceSaluja-hs2fh]

one of the best teaching style .. but i guess after explaining the concept, if you dry run the final code ..then may b student will get more clear..apart from this rest everything is perfect..

[@bhaveshkumar6842]

Very well explained as always. You sir are a legend!

[@KartikeyTT]

We can get a O(n) time complexity for the first code if we modify the code to find the height of a binary tree. Here is the code int maxDepth(TreeNode* node,int& maxi){ if(node==nullptr){ return 0 ; } int l=maxDepth(node->left,maxi); int r=maxDepth(node->right,maxi); maxi = max(maxi,l+r); // check the max diameter at each function call return 1+max(l,r); } int diameterOfBinaryTree(TreeNode* root) { int maxi =-1; // initialise maxi to -1 maxDepth(root, maxi); // pass maxi by refernce return maxi; }

[@pratyush2331raj]

better than love babbar's approach. I am enjoying your tree series. It's truly amazing🔥🔥

[@lifehustlers164]

Completed 17/54 (31% done) !!!

[@easycode3189]

simple Explanation || Easy to Understand || Thanks Alot for Valueable Effort

[@SaadKarim-r6z]

diameter =max(diameter,lh+rh+1); as the node will itself include in the diameter part

[@pritam7461]

diameter will be equal to max(diameter,lh+rh+1). The +1 is missing

[@pankajjangra7]

+1 is not required here, because the question(on leetcode) says diameter as number of edges. And in a tree, the number of edges are one less than the number of nodes. So it works fine.

[@sangharshpipare666]

I tried on my own using Java couldn't get to the solution. Nice explanation

[@1712NineNine]

wow I was thinking of creating a global variable but i never realized we can just pass by a variable by reference too by putting it in a single sized array!!!

[@ramandeepsingh8464]

We can use a static variable also bro

[@RajivKumar-qj9nw]

Node need to pass array of size 1. class Solution { private int maxDia = 0; public int diameterOfBinaryTree(TreeNode root) { getDia(root); return maxDia; } public int getDia(TreeNode root){ if(root == null) return 0; int lh = getDia(root.left); int rh = getDia(root.right); maxDia = Math.max(maxDia,lh+rh); return 1 + Math.max(lh,rh); } }

[@SchrodingerMan]

// brute force int height(TreeNode* root){ if(root==NULL) return 0; int x=height(root->left); int y=height(root->right); return max(x,y)+1; } int maxi=0; int diameterOfBinaryTree(TreeNode* root) { if(root==NULL) return 0; int x=height(root->left); int y= height(root->right); maxi=max(maxi,x+y); int left= diameterOfBinaryTree(root->left); int right=diameterOfBinaryTree(root->right); return maxi; }

[@MischievousSoul]

Isn't this code giving error??

[@kistareddy5361]

well explained 🦁

[@rohan8758]

It was awesome explanation Raj bhaiyan, you did a great job.

[@stith_pragya]

Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@yashtyagi8040]

very clear explanation dry run clear all the doubt thank you sir

[@VarunKumar-eq2ox]

please do series on binary search and greedy algorithms

[@nikitakeshri9233]

Beautifully explained

[@user-fw4kz3bb4g]

u are beautiful

[@Rahul_Mongia]

**JAVA CODE** class Solution { int diameter=0; public int diameterOfBinaryTree(TreeNode root) { if(root==null) { return 0; } helper(root); return diameter; } public int helper(TreeNode node) { if(node==null) { return 0; } int lh=helper(node.left); int rh=helper(node.right); diameter=Math.max(diameter,lh+rh); return 1+Math.max(lh,rh); } }

[@cinime]

Understood! Such a great explanation as always, thank you very much!!

[@rajsaraogi]

@12:50 to use pass by reference Code for GeekforGeek answers int diameter(Node root) { int[] diameter = new int[1]; findMax(root,diameter); return diameter[0]+1; // Your code here } int findMax(Node node, int max[]){ if(node == null) return 0; int leftH = findMax(node.left, max); int rightH = findMax(node.right, max); max[0] = Math.max(max[0],leftH + rightH); return 1 + Math.max(leftH,rightH); }

[@SatyaMantha]

Striver, please make string and heap series

[@atharvdeshmukh8953]

Nice trick (0 length array) for java code at the end. I was thinking of using static variable.

[@anshvashisht8519]

why is array used?

[@jitinroy2246]

@@anshvashisht8519 +1

[@pqrstwxyz1175]

​@@anshvashisht8519in Java it is pass by value and not reference but array it self is a reference to a object in heap memory, where a normal variable like int, float are not pointing or referencing to any address.

[@ujjwalpratap8729]

Very well Explained , Thanks for clearing the doubts

[@studyonly9622]

int helper(TreeNode*root,vector&vec){ if(root==NULL)return 0; int l = helper(root->left,vec); int r = helper(root->right,vec); vec.push_back(l+r); return 1+max(r,l); } int diameterOfBinaryTree(TreeNode* root) { vector vec; helper(root,vec); sort(vec.begin(),vec.end()); return vec[vec.size()-1]; } This is what i did before watching this video.

[@vaarigupta6332]

Nice solution - Simplest of all of studied so far

[@nawabkhan4916]

great work, and have lots of sponsor ad so that you can provide great videos.

[@pervejmia8240]

what is the space complexity of your first approach? O(n) for recursion stack memory?

[@kanishkgoel5946]

Easier solution: class Solution { private: int maxDepth(TreeNode* root) { if(root==NULL) return 0; int left = maxDepth(root->left); int right = maxDepth(root->right); return 1+max(left,right); } public: int diameterOfBinaryTree(TreeNode* root) { if(root==NULL) return 0; int left = maxDepth(root->left); int right = maxDepth(root->right); int ld = diameterOfBinaryTree(root->left); int rd = diameterOfBinaryTree(root->right); return max(left+right, max(ld,rd)) ; } };

[@hassankazmi5443]

very good job sir, beautifully simplified

[@hareshnayak7302]

Thanks striver for this amazing video.

[@bhavkushwaha]

Thankyou Striver, Understood!

[@rishavyadav9438]

If you wonder how to write JAVA solution without Array int maxDiameter=0; //Declare class instance variable and using 'this' we can modify its value in function which will reflect here as well this.maxDiameter=Math.max(this.maxDiameter,leftHeight+rightHeight);

[@wolfieymozart]

hi can you explain this or give the full code

[@sravan8643]

My Solution: class Solution { public: int maxi; Solution(){ maxi=0; } int diameterOfBinaryTree(TreeNode* root) { maxHeight(root); return maxi; } int maxHeight(TreeNode* root){ if(root==NULL) return 0; int lst=maxHeight(root->left); int rst=maxHeight(root->right); maxi=max(maxi,lst+rst); return 1+max(lst,rst); } };

[@golubhattuk01]

thank you sir ji for this series

[@codeman3828]

Great video. Understood

[@AmanYadav-jf1yy]

Code for Naive approach int findh(TreeNode* root) { if(root==nullptr) return 0; int lh=findh(root->left); int rh=findh(root->right); return 1+max(lh,rh); } void solve(TreeNode* root, int &ans) { if(root==nullptr) return; int lh=findh(root->left); int rh=findh(root->right); ans=max(ans,(lh+rh)); solve(root->left,ans); solve(root->right,ans); } int diameterOfBinaryTree(TreeNode* root) { if(root==nullptr) return 0; int ans=0; solve(root,ans); return ans; }

[@DeepakKumar-yc9hr]

Thankyou bhaiya for Tree Series

[@funnyanimation888]

It was really a good explanation of the algo.

[@at_your_techbuddy]

Sir, can you please tell what is the reason you usually define helper functions like height of "private" type?

[@virusdgamer8804]

cuz functions outside of class Solution dont need to access the height function. As you already know that it is a HELPER FUNCTION, we only want diameterOfBinaryTree func to access it and not the functions outside of the class.

[@at_your_techbuddy]

@@virusdgamer8804 got it thanks!!

[@mriduljain1981]

completed lecture 16 of Tree playlist.

[@anssha2643]

Thanks for explanation. It the best I have seen so far.

[@kasyapdharanikota8570]

very well explained

[@apmotivationakashparmar722]

Thank you so much.

[@26-tycm-i-durveshjagtap26]

Best explanation and approach so far!!!

[@DeadPoolx1712]

UNDERSTOOD;

[@Rajat_maurya]

which is better practice a global variable or passing in function?

[@arnabdutta4662]

passing in function

[@shrirambalaji2915]

Thank you Brother, This series indeed helping me and Thousands of other people

[@anmolverma075]

In the final code of Java , I tried taking a maximum variable instead of taking the array . Why is the code not working in this case? Cany anyone explain me this?

[@ishangujarathi10]

love your intuition, understood completely

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@hardkapadia5633]

This was a fucking genius solution hats off man

[@adebisisheriff159]

Thanks Striver!!!

[@abhishekkumarsingh8603]

bhaiya array banane ki jagah class variable bana denge toh bhi kaam kar hi jana chahiye kyonki motive toh yehi hai na ki multiple copy na bane recursion call pe

[@takeUforward]

Hnn kese v kro krne se mtlb h :P

[@whyashu]

PYTHON: class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: self.d=0 def height(root): if not root: return 0 l=height(root.left) r=height(root.right) self.d=max(self.d,l+r) return 1 + max(l,r) height(root) return self.d

[@hjklmn9526]

Cool, I didn't understand though how the brute force solution was O(N^2). Plus, in your final solution, you could have simply maintained the max_diameter as a class level variable instead of passing a 1 element array for each recursive call..

[@piyushacharya7696]

global variables are not quite good to use, and since the variables are not passed by reference in java using the array of size 1 works just fine.

[@hjklmn9526]

@@piyushacharya7696 This is a single-threaded execution. And I talked about an instance variable of the class. Not global variable.

[@sumit_verma_77]

Have you got it ?? I have same doubt because i think that code will give us everytime 0 in maxi variable.

[@parthsalat]

Thanks a lot!

[@namanlakhwani4752]

I'm not passing diameter variable in helper function instead defining in globally. Any disadvantage of this approach? class Solution { public: int dia=0; int diameterOfBinaryTree(TreeNode* root) { height(root); return dia; } int height(TreeNode* root){ if(root==NULL) return 0; int lh=height(root->left); int rh=height(root->right); dia=max(dia,lh+rh); return 1+max(lh,rh); } };

[@rakshitpuri4192]

Use of global variable is discouraged so we should avoid them.

[@adityarajsingh8110]

What you can do is pass a reference integer to diameterOfBinaryTree() so your function will look like diameterOfBinaryTree(TreeNode* root, int& maxi)

[@Yash-uk8ib]

@@rakshitpuri4192 yes it is!! can u say me the reason behind it??

[@adityan5302]

Python O(n2) solution Brute Force Approach Only visit if you face difficulty in writing code... def height(root): if root is None: return 0 l=height(root.left) r=height(root.right) return max(l, r)+1 def diameter(root, maxi=-9999): if root is None: return lh=height(root.left) rh=height(root.right) maxi=max(maxi, lh+rh+1) diameter(root.left, maxi) diameter(root.right, maxi) return maxi

[@UECAshutoshKumar]

Thank you sir

[@rahulsinghshekhawat2487]

Nice explanation.

[@adityavaste8963]

Great Explanation 👍

[@zodiacsama7693]

why we used referencing while passing diameter to the height function

[@jazzbeat4443]

dude explain with recursion stack memory allocation and deallocation diagrams , it will help us understand better about recursive calls

[@ManishKumar-qs8xh]

yes, yes, find height wala code

[@himanshidafouty347]

Understood

[@bhagyashreekhairnar683]

Thank you

[@349_rahulbhattacharya6]

understood thankyou so much

[@magnitegame]

striver what a easy concept and solution and different one

[@auroshisray9140]

i love the way you teach

[@nikhilkumarjamwal5322]

Nice Explanation!👍

[@KartikeyTT]

tysm sir

[@spandanrastogi7144]

JAVA BRUTE FORCE : private static int findHeight(TreeNode root){ if(root == null) return 0; int leftHeight = findHeight(root.left); int rightHeight = findHeight(root.right); return 1 + Math.max(leftHeight, rightHeight); } int dia = 0; public int diameterOfBinaryTree(TreeNode root) { if(root == null) return 0; int leftHeight = findHeight(root.left); int rightHeight = findHeight(root.right); dia = Math.max(dia, leftHeight + rightHeight); diameterOfBinaryTree(root.left); diameterOfBinaryTree(root.right); return dia; }

[@ankitasinha9912]

Hi Shouldn't maxi =Math.max(maxi,1+lh+rh) ?

[@K-Raman]

yes, because if test for only one node it return 0 diameter. So, you are correct. it should be max =Math.max(diameter[0],1+lh+rh);

[@ganeshkamath89]

Thanks Striver

[@drdominance9392]

Great video striver, Will maxi value remain same on going to right tree after left tree traversal? I'm not getting the point where maxi value not change after left tree traversal Someone please help 🙏🙏🙏🙏

[@chandantaneja6388]

think maxi is like updating each time when it encounters some greater value. make it global it will work good, so that you can access outside the function.