Diameter of a Binary Tree | Diameter of a Tree | Maximum width of Binary Tree | DSA-One Course #63

[@AnujBhaiya]

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.

[@shrinivaskathare3444]

thanks for this msg , I was confused becoz on leetcode it is lh+rh and on gfg it is lh+rh+1 😄👍❤

[@tarunupadhyay5336]

Very nice explanation boss, please upload videos frequently so that we can finish our learning rapidly.🙂

[@piglets_1992]

Loved the dry run!!! I think we do not need add +1 for the cases when we include the root.

[@bhaskarbhanu2]

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

[@sriramulavenkatakrishnakar9615]

Always there for u bhai .started watching from starting video

[@tonyconor681]

The best & simple explanation thanks for teaching us free of cost

[@sarthakchauhan8386]

Really cool solution bhaiya. Animation walo ke O(n) solution ne to dimag chakra diya tha.

[@RohitKumar-ci7gh]

one correction in above code, don't use +1 in cur

[@syedabdulwahab4729]

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!

[@sufyanahmed6268]

Imagine will get the heart from Anuj bhaiya 😍❤

[@kshitijgaur9635]

Bhaiya your solutions are very simplified, easy to understand 😊

[@abhishekjha3775]

Great 👌🥰💯

[@sahidkhan-ik4lz]

Great explanation 👍

[@Infinite-Scrolling]

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

[@sarthakjain7605]

Please upload more DSA videos

[@siddharthpunmiya0705]

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

[@PatelJiNITian]

sum would be sum= Math.max(sum,lh+rh); then it runs;

[@priyankashaw1238]

what is the point of storing data in ans when we are not finding max between ans and max(lh,rh) . Pls explain

[@siddharth.chandani]

Doing *DRY RUN* of the code is just 🔥

[@lalithabhavani2016]

Hi! In the last example isnt the diameter of the tree 3?

[@pratosh]

bro waiting for graph and DP concepts.....my amazon interview may come any time.

[@ayushjaiswal5324]

There is a minor correction in the solution. At the time of calculating the "ans", we should not add 1.

[@wordsofpunjab5134]

Please let me know how to get the nodes that make that max diameter as well.

[@fardilviews]

Love from Bangladesh.

[@reenayadav8468]

Thank you so much . u are the best👍💯

[@shashanksingh4708]

what are we doing with the ans variable

[@nishudwivedi3478]

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

[@divyanshmishra5121]

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

[@89Bhim]

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.

[@therealsumitshah]

You got placed bro?

[@sabyasachisahoo8975]

but in result ,,you need to -1 from ans.................cout

[@bhushankorg5606]

nah bro its works fine

[@gangstaplays2715]

@@bhushankorg5606 no, check leetcode question, you have to return ans-1

[@abhaykaushik95]

1000th like

[@kumarrohit8311]

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

[@SanchitTewari]

How? TC cant go below O(N). You have to visit all the nodes atleast once I dont think this hashmap approach is recommended

[@anshumaan1024]

bhaiya aapne title me maximum width likha hai par, video me pdaya hi nhi 🙄

[@vimalslab3398]

Mast😎

[@yashyadav7927]

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?

[@bhavialkhaniya1110]

nice

[@tushargupta9428]

is the playlist complete

[@nishudwivedi3478]

No

[@sahilkumar4078]

@Anuj Bhaiya this video is coming hidden in the playlist DSA -one course pls CHeck!!!

[@49mukund60]

Kitne total video aayenge is series me??

[@gauravparasar4571]

sir code ko laptop me kia karo plsss

[@mansijangid8017]

Bhaiya next video kab tk aayegi🙂??

[@swarupmondal3942]

dsa ka new video kab agega?????😢😢😢

[@good114]

💕❤️

[@subhankarpal2800]

❤❤❤❤❤❤🙏🙏🙏🙏🙏🙏

[@RiyaGhosh-dq9fq]

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

[@sumitkanth5349]

Gsoc 2022 ki video bnado from scratch.. Plz...... I know Javascript

[@farhanmuhamed392]

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

[@wordsofpunjab5134]

Please let me know how to get the nodes that make that max diameter as well.