Diameter of a Binary Tree | Diameter of a Tree | Maximum width of Binary Tree | DSA-One Course #63
Вставка
- Опубліковано 8 лют 2025
- Hey guys, In this video, We're going to solve another problem on Binary Trees called calculating the Largest path between two leaf nodes aka calculating the diameter of a binary tree.
📍Join my paid Java DSA course here: www.codingshut...
📍Spring Boot 0 to 100 course: www.codingshut...
📍React 0 to 100 course: www.codingshut...
🚀 Follow me on:
Instagram: / anuj.kumar.sharma
Linkedin: / sharma-kumar-anuj
X: x.com/sudoanuj
Hashtags:
#anujbhaiya #dsaone
Tags:
diameter of binary tree
diameter of a binary tree
anuj bhaiya
diameter of a tree
diameter of tree
543. diameter of binary tree
maximum width of binary tree
anuj bhaiya java
largest distance between nodes of a tree
binary tree diameter
dsa one
binary tree maximum path sum
diameter of binary tree in c
anuj bhai
diameter
diameter of binary tree python
maximum path sum between 2 leaf nodes
tree diameter
width of binary tree
anuj bhaiya dsa
bottom view of binary tree
dp on tree
height of binary tree
ishan sharma
max width of binary tree
maximum depth of binary tree
On Leetcode, the diameter of a tree is defined as the largest number of edges between the two nodes. Here, I am assuming diameter as the largest number of nodes between the two nodes. Hence to make this code work on leetcode, Just remove the addition of 1 from 1 + lh + rh in the second method.
thanks for this msg , I was confused becoz on leetcode it is lh+rh and on gfg it is lh+rh+1 😄👍❤
Very nice explanation boss, please upload videos frequently so that we can finish our learning rapidly.🙂
Hi Anuj, thanks for your videos, i have a suggestion which may be even more helpful for the professionals. Most of the time when we talk about DS based algos, they look important only from the perspective of interview, which is kind of underplaying such important concepts. I would very much be interested in knowing your experience or understanding of using these in some real world projects
Always there for u bhai .started watching from starting video
The best & simple explanation thanks for teaching us free of cost
Really cool solution bhaiya. Animation walo ke O(n) solution ne to dimag chakra diya tha.
Loved the dry run!!! I think we do not need add +1 for the cases when we include the root.
I've watched other videos too where they have to introduce some arithmetic to come up with a O(n) solution but this solution is a beauty. Simple, Elegant, Fast. Keep on inspiring Anuj Bhaiya!
one correction in above code, don't use +1 in cur
Imagine will get the heart from Anuj bhaiya 😍❤
class Solution {
// in case u don,t know how to return ans....
int diameter(Node root) {
// Your code here
height(root);
return ans;
}
int ans=0;
int height(Node root){
if(root==null)return 0;
int lh=height(root.left);
int rh=height(root.right);
ans=Math.max(ans,rh+lh+1);
return 1+Math.max(lh,rh);
}
}
Bhaiya your solutions are very simplified, easy to understand 😊
Great 👌🥰💯
Bro second method mai +1 mat karo answer wrong hoga i have coded with the same idea and without adding +1(in 1+lh+rh) we can get the correct ans
Great explanation 👍
Please upload more DSA videos
Love from Bangladesh.
bro waiting for graph and DP concepts.....my amazon interview may come any time.
sum would be sum= Math.max(sum,lh+rh);
then it runs;
There is a minor correction in the solution. At the time of calculating the "ans", we should not add 1.
class Solution {
public:
int ans = INT_MIN;
int height(Node * root)
{
if(root== NULL)
return 0;
int lh = height(root->left);
int rh = height(root->right);
ans = max(ans, 1+lh + rh);
return 1 + max(lh, rh);
}
int diameter(Node* root)
{
height(root);
return ans;
}
};
what is the point of storing data in ans when we are not finding max between ans and max(lh,rh) . Pls explain
Hi Anuj, watched all 63 videos of DS, very well explained. Can you please make videos on more Graph probles(bfs & dfs slready made) and dynamic programming problems. You mentioned about techie delight in one of your video but that's not in video form( I am preparing for G/A interview is gointo held in Feb, I message you on Instagram as well but I guess you didn't see that)
Thanks in advance.
You got placed bro?
Thank you so much . u are the best👍💯
Bhaiya please or videos upload kro others topics pr please bhaiya...... Please, hm poora aap hi pr depend h please bhaiya.... Upload the videos..... Aap is course ko kb tk complete krdoge bhaiya....... Bhaiya please reply....
Hi! In the last example isnt the diameter of the tree 3?
Bhaiya, if I use the below method to calculate height using diameter and getHeight function, the complexity would be reduced to O(nlogn). Correct na?
I am using a Hash-Map so that the we don't have to compute the height from the visited nodes.
Scala code
// Get the height of a given node
// Example:
// 3
// / \
// 2 4
// / \
// 1 5
// Node: 4, Height: 2
// Node: 2, Height: 1
// Node: 1, Height: 1
// Node: 5, Height: 1
var hashMap : HashMap[Node, Int] = HashMap[Node, Int]()
def getHeight(root: Node) : Int = {
if(root == null)
return 0
if(hashMap.contains(root))
hashMap.get(root).get
else{
val leftHeight = getHeight(root.left)
val rightHeight = getHeight(root.right)
val currHeight = math.max(leftHeight, rightHeight) + 1
hashMap += root -> currHeight
currHeight
}
}
How? TC cant go below O(N). You have to visit all the nodes atleast once
I dont think this hashmap approach is recommended
Doing *DRY RUN* of the code is just 🔥
Please let me know how to get the nodes that make that max diameter as well.
what are we doing with the ans variable
1000th like
nice
bhaiya maine 7 bar video dekha but end part aabhi tak nahi samja
aap plz ek ek steop jaise height of binary tree mai explain kiya tha bata sakte ha?
but in result ,,you need to -1 from ans.................cout
nah bro its works fine
@@bhushankorg5606 no, check leetcode question, you have to return ans-1
sir code ko laptop me kia karo plsss
bhaiya aapne title me maximum width likha hai par, video me pdaya hi nhi 🙄
Mast😎
@Anuj Bhaiya this video is coming hidden in the playlist DSA -one course pls CHeck!!!
Kitne total video aayenge is series me??
is the playlist complete
No
💕❤️
Bhaiya next video kab tk aayegi🙂??
❤❤❤❤❤❤🙏🙏🙏🙏🙏🙏
dsa ka new video kab agega?????😢😢😢
Sir please ek request hai ki subtitles daliye English and other indian and foreign languages mei taki baki log jan sake aware and learn kare..please sare videos mei baki subtitles daliye 2nd channel pebhi sir
Gsoc 2022 ki video bnado from scratch.. Plz...... I know Javascript
+1 is not needed, cuz diameter is calculated not in no of nodes. it in edges
int diameterOfBinaryTree(TreeNode* root) {
if (root == nullptr)
return 0;
int leftTreeHeight = height(root->left);
int rightTreeHeight = height(root->right);
int leftDiameter = diameterOfBinaryTree(root->left);
int rightDiameter = diameterOfBinaryTree(root->right);
return max({leftTreeHeight + rightTreeHeight, leftDiameter, rightDiameter});
}
Please let me know how to get the nodes that make that max diameter as well.