Diameter of a Binary Tree | Solution | Binary Tree | Data Structures and Algorithms in JAVA
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we explain the solution of where we are required to find the diameter of a binary tree in minimum time and space complexity. To understand more about this question, click here:
For a better experience and more exercises, VISIT: www.pepcoding....
#pepcoding #programming #onlinecourses
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Please everyone make this channel as famous as possible.
Thank you so much sir for such a clear explanation. I can now provide the interviewer with 3 different approaches for finding diameter (including generic tree approach). All thanks to you ❤
wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit. If you like our efforts, we request a review
g.page/Pepcoding/review?rc
@@Pepcoding Sure sir and thank you so much sir ❤
Sir i did this question using the same approach that we folllowed in Generic Tree
//The approach
static int dia=0;
public static int diameter1(Node node) {
if(node==null){
return -1;
}
int lh=-1;
int slh=-1;
int lch=diameter1(node.left);
if(lch>lh){
slh=lh;
lh=lch;
}
if(lch>slh){
slh=lch;
}
int rch=diameter1(node.right);
if(rch>lh){
slh=lh;
lh=rch;
}
if(rch>slh){
slh=rch;
}
if(lh+slh+2>dia){
dia=lh+slh+2;
}
lh++;
return lh;
// write your code here
}
Then print dia in the main function
Awesome explanation your videos explanation are so down to earth, so simple, raw explanation I feel like my friend is teaching me.🔥🔥❤️❤️
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Gave this question 2 hrs and totally worth.
Great explanation Sir
Great teacher
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review - g.page/Pepcoding/review?rc
@@Pepcoding sir I have already given the review with lots of love sir❤️❤️
@@harshitkaushik4144 solution is of 35minutes, and you gave 2 hours for it....YOU MUST BE A SLOW LEARNER :(
every minute i watched is worth it.
Glad to know that you liked the content and thank you for appreciating.
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
That was really helpful, Thank you sir
Didi sir ka chaneel bhi promote kar do
the length of the video is slightly more than others but it is definitely worth it,
thanks sir.
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Tricky solution 😅. Do baar dekhna pad gya 2nd method ke liye. As always Thanks sir.❤️
2 kyunn 4 brri dekho aap😅 jb tkk crystal clear na hojaae as always thank you very much !! keep watching and share kijiee apne friends ke sth...
sir inefficient ki time complexity o(n^2) nhi hai o(nh) where h is the height of the tree
because if we visit every node for every particular node then it would be O(n^2)
but here we are visiting till height of tree from that particular node so TC will be O(nh)
//first = height // second = diameter
pair HeightDiameter(BinaryTreeNode*root)
{
if(root == NULL)
{
pair bc(0,0);
return bc;
}
pair lans = HeightDiameter(root->left);
pair rans = HeightDiameter(root->right);
pair ans;
ans.first = 1 + max(lans.first,rans.first);
ans.second = max(lans.first+rans.first,max(rans.second,lans.second));
return ans;
}
Mza aa gya sir ye video dekke. Iska approach to mai ab kbhi nhi bhulunga. Tilt wala question ke videos kb upload honge sir?
5-6 August ke aaspaas
One of the deepest discussion on binary tree
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
Accha kaam ker rahe ho dost...Tareeka bahut acha hai...
Everything is detailed amazing Content 🔥
Sir this can easily be done in O(n) using a static variable:-
static int maxDiam=Integer.MIN_VALUE;
public static int diameter1(Node node) {
// write your code here
if(node==null){
return -1;
}
int ld = diameter1(node.left)+1;
//height of left node till current node
int rd = diameter1(node.right)+1;
// height of right node till current node
int cd = ld+rd;
//current node diameter
if(cd>maxDiam)
maxDiam=cd;
//updating max diameter
return Math.max(ld,rd);
//returning the max of left height and right height, this value will help its parent node
}
Beta, saari possible approaches pdege aap. By the end of level-3 har question ki apko best approach pta hogi.
@@Pepcoding haan sir abhi aage ke problems mein pata chala ki yeh problems travel and change aur class wali method se interchangeably kr skte h
I love your mathematics I code in c++ but watch your videos for understanding the concept...
Thanks man
Glad you like them! For better experience visit on nados.pepcoding.com
Suppose A is the Root node ,Then Diameter will either include that node or exclude that node.
Then the
Three factor are:
1)If the diameter include(Passes through) the root,then the diameter will be Lheight+Rheght+2
2)Diameter exclude the root and lies in the left subtree
3)Diameter Exclude the root and lies in the right subtree
Hence Overall Diameter will be maximum of these three factors.
Magic kya tha ? Sir, magic toh aap ho !🙏
sir i am learning coding in python. but the way to solve the problems so unique and good. thats why everyone gets comfortable over here. sir please python mein bhi bna do videos
Beta, interview main bhot he thore interviewer apko python main code krne ki freedom dete h, nh to 95% of the companies apko cpp ya java main he code krne ko deti h
//dia ko static bhi rkh skte hai
int diameterAndReturnheight(Node* root, int& dia) {
if(root == NULL) return -1;
int lh = diameterAndReturnheight(root->left, dia);
int rh = diameterAndReturnheight(root->right, dia);
if(dia < lh + rh + 2) {
dia = lh + rh + 2;
}
return max(lh, rh) + 1;
}
tum toh bde heavy coder nikle
@@vikasjoshi7236 tu dubara ku dekh raha
basically sir humne height ka function use karne ki jagah DiaPair waale function mein hi height calculate karli dia ke saath saath.
Great video, very easy to understand 👏
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
th-cam.com/users/Pepcodingabout?view_as=subscriber
You are "the" best teacher!! ❤️
keep motivating, keep learning and keep loving Pepcoding😊
Dusre to sirf padhate hai, sir feel kra dete hai💓
Thanks a lot
For better experience visit- nados.pepcoding.com
Don't forget to follow us on Instagram
instagram.com/pepcoding/
bahut maza aaya sir
Sir kya hmlog ek global variables ka use kr k answer nhi nikal sakte the jis tarah se humne generic tree me diameter nikala tha ?
ofcourse. ye doosra style hai. pair style and change and return style. Is tarah ke sare questions mei do tareeke hote hain
sir jaise humne generic tree me nikala tha diameter vaise nhi kr sakte ?
Mazaa aa gaya sir ekdum....Amazing🙌
Shukriya ji!
Bs aise he pyaar bnaye rkhe aur pdte rhe😊
very deeper explanation (lbrain + rbrain + infinty)
nice explanation really worth it.
It was totally mind blowing question sir, ur great🔥
Glad to know that you liked the content and thank you for appreciating. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
always the great explanation from you sir, thank you so much
My pleasure!
Very nice trick. Very well used of OOPS
Thankyou beta!
I am glad you liked it. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
My mind is fucked after watching the 2nd approach but in a good way.
Thank you sir we can see ur dedication.
Thanks buddy!
I am glad you liked it. I hope that you are watching the videos till the end. If you like our efforts, will you like to write a review about us here - g.page/Pepcoding/review?rc
sir aapne bola tha ki paid and free courses mein sirf mentoring ki difference hai... But neeche kuch comments mein aapne bola ki paid has more stuffs. Sir aapne baad mein saare content free karr diye kya ki abhi bhi kuch resources extra hai on paid course?
btw the explanation was fanstastics as always
sir, is this code efficient instead of creating DiaPair class ?
static int fdia = 0;
public static int diameter1(Node node) {
// write your code here
if(node == null){
return -1;
}
int Lht = diameter1(node.left);
int Rht = diameter1(node.right);
int dia = Lht + Rht + 2;
fdia = Math.max(fdia,dia);
return Math.max(Lht,Rht) + 1;
}
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
Okay sir no problem, glad that you replied 😊
Looking forward to join your placement program in center...
Good use of the 'travel and change' strategy
sir I have implemented the same approach as of generic tree. sir can we consider it as efficient or not
static int dia;
public static int height(Node node) {
if (node == null) {
return -1;
}
int lh = height(node.left);
int rh = height(node.right);
int d = lh + rh +2;
dia = Math.max(dia , d);
int th = Math.max(lh, rh) + 1;
return th;
}
public static int diameter1(Node node) {
dia=0;
int h = height(node);
return dia;
}
correct
Great Explanation
Great
Sir I have completed this foundation series. What should I do next ?
😊😊😊😊Awesome explanation
Sir aapke TH-cam videos me and aapke online course wale videos me koi difference hai ??
Bcoz me b join krunga aapka pepcoding isi saal....plzz reply sir🙏
hanji, ye poora nahi hai. wahan jyada content hoga.
@@Pepcoding what
Please add tree views too.. Left, right, bottom, top and boundary of tree
ji
Note to self - height function returns -1 in NULL
Sir pls make some videos on dp
Epic explanation sir!!
Glad you liked it
Thank you very much sir
In post order we created an object, so on every recursive call a new object will create ?
very nice explaination ,thank you
Glad to know and thankyou for appreciating. If you like our efforts, will you like to review us here - g.page/Pepcoding/review?rc
Too GOOD !!!
Sir isBST and largestBST ki bhi video upload kar dijiye
ok ji
@Pepcoding agar sirf 2 node hoo toh . iska answer 1 hai and lekin sir aapke logic se minimum answer 2 hai joo ki galat hai. means only root and root->left.
recursion waale method me
Return -1 in base case if you are finding in terms of edges .
public static DiaPair diameter2(Node node)
what does this line do?
I can see a name after a predefined class name what is that used for?
sir, diameter ko static variable lekr or easy nahi ho jayega?
Sir Can you explain the approach of travel and changing method for this question???
read harish kumar comment on this video
int ans=0;
int height(Node*root)
{
if(root==NULL)
{
return 0;
}
int left=0;
int right=0;
left=1+height(root->left);
right=1+height(root->right);
// cout
fes is not the best name, it may be named iod, its own diameter, i.e. the 'diameter' made when it passes through the current node
Not able to see the playlist of binary tree level 1.
Sir, jo approach generic tree me li thi dch(deepest child height) and sdch(second deepest child height) , usse yeh approah kaise better hai? Dono O(n) hai
Bro in genric tree hight ke liye alag se call nhi kri hai post order me her ke node ki hight li hai sir ne uske hisaab se sir ne highest and secend highest set kra hai aur usme first and secend highest esliye liya tha sir ne kyoki usme hme pta nhi tha kiten child hai to un sab me se hme first highest and secend highest lena tha but esme hme pta hai 2 node hai to esme 100 percent ya to pahle bda hoga ya dusra to undono ke liye hight ki extra call kri hai jasse recursion bar bar ho rha hai wo pahla aproh esliye o(n2) hai dusre me sir ne pair class bna ke hight ko sath liya hai as genric tree
yes but he wants to think you in different way too
ofcourse. ye doosra style hai. pair style and change and return style. Is tarah ke sare questions mei do tareeke hote hain
this is 1 reply by sumeet sir on similar kind of question
Esme aap ne bola hai ki last me hem lag se hight ko call kerte hai to whi call hem sath me ker denge pair bnaker kyoki jeb last me call kerte hai to whi recursion fir se hota to wo n elements ko n bar recursion kerna hoota hai
Yes, yehi kha hai
Sir live class ka batch after lockdown live hi continue hoga ki classroom me convert ho jayega?
I m outside Delhi student and want to join levelup but if lockdown opens up i wont b able to come to class in Delhi
live bhi chlta rahega aur classroom bhi, wahin se aage jahan tak classes ho gai thi
I have a doubt... can anyone explain to me the diameter of a Node with Left and Right children as NULL.
for example, if we pass a single root node in a tree then what will be output?
Sir Your student from 2017 CRUX Batch
Will it work to find the diameter of a binary tree?
T.C: O(n)
int dia = INT_MIN;
int func(TreeNode* temp){
if(!temp) return 0;
int x = func(temp->left);
int y = func(temp->right);
dia = max(dia, x+y+1);
return (max(x,y)+1);
}
For better experience and curated content sign up on nados.io and post your queries on community tab of NADOS.
"Mai to saaf likhta tha bhukamp aaya tha isliye gaandi writing thi" that was epic. 🤣
😂
sir recursion wali calls samajh nhi aayi ,kahaan se dekhu?
sir apne low level thinking to karai hi ni ismai smz mai kam aya
Sir Binary tree or BST level1 ki enough hai? ya or karna chhaiye?
Aur karna hoga
Which tool do you use sir for copy paste the image?
For better experience and precisely arranged videos.
Visit - nados.pepcoding.com and sign up to NADOS.
Don't forget to follow us on Instagram instagram.com/pepcoding/
public int diameter(Node temp) {
if(temp==null)
return 0;
if(temp.left==null && temp.right==null)
return 1;
int ld = diameter(temp.left);
int rd = diameter(temp.right);
int maxht = ld+rd;
// if(ld!=0 && rd!=0)
// maxht+=2;
// else if(ld==0 && rd==0)
// maxht+=0;
// else
// maxht+=1;
maxd = Math.max(maxht, maxd);
return Math.max(ld,rd)+1;
}
prog.java:105: error: cannot find symbol
DiaPair p=new diameter2(root);
^
symbol: class diameter2
location: class Solution
I am getting this error.
Sir, I implemented the same code but still the answer is wrong on the lead code problem leetcode.com/problems/diameter-of-binary-tree/
When I do not add 2 to the heights it is giving me the correct answer can you explain that?
beta ek baat ka dhyaan dena, ki diameter edges mei count kia hai ya nodes me. dono implementations mei farak hota hai. Dekho jra leetcode ne kaunsa maanga hai.
@@Pepcoding Sir leetcode mein edges maanga hai, and uske hisabh se to +2 hona chahiye. Please explain sir.
@@parissweetheart96 make sure to return -1 in the base case if you require to find edges, and return 0 in base case if you are asked to find nodes
sir what is euler?
Sir esme bhi faith and expection wala kam hai
Yes most of the tree question is like that
sir lh +rh+1 nhi hoga
hmmm yeh mere ko bhi confusion hai. video mein lh+rh+2 bola hai. but actually mein +1 hota hai
Aur new videos kyu nahi arahe???
firr shuru hone wali hain
@@Pepcoding Finally some god news, sir jaldi jaldi upload kar dijiye
+2 krna smjh nhi aaya : )
Sir even after not specifying the cases where the diameter is not counted from the root then also I am passing all the test cases in pepcoding .
public static int diameter1(Node node) {
// write your code here
if(node == null){
return -1;
}
int h1 = height(node.left);
int h2 = height(node.right);
int dia = h1+h2+2;
return dia;
}
test case weak hain beta hmare.
@@Pepcoding okay sir
Sir is this the same course you're providing for 12000?
ye usme se kuch kuch hai beta.
demo ke liye dala hai
Okay sirr
@@Pepcoding 😁😄
Ek chor tarika dekho dosto!
public static int height(Node node) {
if (node == null) {
return -1;
}
int lh = height(node.left);
int rh = height(node.right);
int th = Math.max(lh, rh) + 1;
return th;
}
public static int diameter1(Node node) {
int ht1 = height(node.left);
int ht2 = height(node.right);
return ht1+ht2+2;
}
For better experience and well organised content, sign up on nados.io and take your preparation to the next level.
public class Solution {
static int diameter;
public int solve(TreeNode A) {
diameter = 0;
height(A);
return diameter;
}
public static int height(TreeNode root) {
if (root == null)
return -1;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
diameter = Math.max(diameter, 2 + leftHeight + rightHeight);
return 1 + Math.max(leftHeight, rightHeight);
}
}
public static int diameter1(Node node) {
// write your code here
if(node == null) return 1;
int leftEdge = height(node.left)+1;
int rightEdge = height(node.right)+1;
return leftEdge+ rightEdge;
}
It was more confusing than it has to be, sir; Attentions span hi nahi hota itna, normal insaan ka.
Please try hard. Genuine content takes time.
Please add tree views too.. Left, right, bottom, top and boundary of tree
ji beta. very soon
Great