here actually l and r are returning the heights of the left and right subtrees, not the diameters. Coz the diameter of the whole tree is basically the maximum value of (l + r + 1) for every node, this is what being done here.
exactly because my diameter is alwaya lh +rh +1 in all cases so res=INT_MIN; then we can find out only matter of fact is I need the maximum left height for root left and maximum right height for roots right so my induction return type will be 1+max(lh,rh); /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int solve(TreeNode* root,int& ans ){ if(root==nullptr){ return 0; } int lh=solve(root->left,ans); int rh=solve(root->right,ans); int temp=1+max(lh,rh);
ans= max(ans,lh+rh+1); return temp; } int diameterOfBinaryTree(TreeNode* root) { int ans=INT_MIN; solve(root,ans); return ans-1; } };
47 of 50 (94%) done! As others have mentioned comparing temp with 1+l+r is not reqd. Also, if we replace temp with what it truly is (height of cur node, max depth from cur node, etc.), then it would be clear. Similarly, ans = cur_dia
In this code the number of nodes are being counted but we need to find (depth of left tree + depth of right tree). In this code a correction needs to be done. We have to return res-1 to ensure that we are not counting the top node of diameter.
baki log to bs video dekh ke waah waah kie ja rhe...........khud se try kr ni rhe bs gyaan pele ja rhe comments me @AdityaVerma please pin this comment otherwise the solution is not submitting
Yes. In the leetcode question, they have specified they need the number of "edges" in the longest path, not the vertices. Number of edges in a tree = number of vertices(nodes) - 1 // basic stuff: 2 nodes are required to make 1 edge, 3 nodes required to make 2 edges and so on. In the above approach what we are essentially calculating is the number of nodes, so in order to return the edge count, we simply reduce the answer by 1. Anyways, this is the best youtube channel to learn DP, period. Huge respect to Aditya. Below is the implementation of this solution in java. We don't need to pass "res" as a method arg, instead we can keep it as global variable class Solution { int finalAnswer = Integer.MIN_VALUE; public int diameterOfBinaryTree(TreeNode root) { func(root); // we don't need the output of this, as "finalAnswer" variable will have the answer return finalAnswer-1; // finalAnswer is the number of nodes, we need to return # of edges, hence -1 } int func(TreeNode node) { if(node == null) return 0; int lsum = func(node.left); int rsum = func(node.right); int toUpperLevel = 1 + Math.max(lsum, rsum); // we need to return this to previous call stack // we dont need to compare the lengths of paths going via current node or via parent node. // 1+lsum+rsum will always have larger value than 1+Max(lsum, rsum) . finalAnswer = Math.max(finalAnswer, 1+lsum+rsum); return toUpperLevel; } }
In a tree, by defn of tree, if there are n nodes, then there are n-1 edges, secondly any subtree in a tree is a tree. That means, the diameter subtree is a tree too, and you can easily switch between nodes/edges by using the n nodes, n-1 edges logic.
Key thing : diameter at each node is defined by 1 + lh (height of left tree) + rh (height of right tree). Just calculate that at each node to get the maximum diameter. Hence use the height method for binary tree and just add the line to calculate the diameter which gives the O(N) solution. The lines marked with --> are the extra lines for the diameter calculation. Rest is the good old height calculation method. Code : --> int ans = Integer.MIN_VALUE; int height(Node root){ if(root== null) return 0; int lh = height(root.left); int rh = height(root.right); --> ans = Math.max(ans, 1 + lh + rh); reurn 1 + Math.max(lh, rh); }
Anuj bhaiya also taught this method! But I didn't realise that time that this is DP. I still can't believe that we are doing DP without memoisation or tabularisation. But I understand that maybe we are using storage plus recursion that's why its DP
For those struggling with the leetcode questions.See Bhaiya is calculating the number of nodes and in leetcode you are asked number of edges so return res-1; class Solution { public: int solve(TreeNode* root,int &res) { if(root==nullptr) return 0; int l=solve(root->left,res); int r=solve(root->right,res); int height=1+max(l,r); res=max(res,1+l+r); return height; }
int diameterOfBinaryTree(TreeNode* root) { if(!root) return 0; int res=INT_MIN; int x=solve(root,res); return res-1; } };
@@abhishekbajaj109Here in the caller function we pass res and in the called function we have &res .This is call by reference.The changes made in the res o the called function will be reflected in the res of the caller function.
Plus diameter is from leaf to leaf right. So I don't think we should compare temp as temp is only from some leaf (other from left or right) to the current node. So there is no sense to include this path because it is not from leaf to leaf. And of course your reason is logical.
yess, But Understand the intuition of Aditya verma for his whole dp series he write one code and do little bit changes for further upcoming same pattern question
bhai...kaha the tum... mai pareshan ho gaya tha ki ye dp kaise hua... yeh to recursion hua hai waise hum node aur diameter ka map banake kar sakte hai dp me
In my knowledge this video is little misleading, actually dp problem tree can be LCA based queries on tree. Same we can use jump pointer to answer efficiently this concept known as binary lifting. Other problems also exist on same line
@@kalagaarun9638 we are returning height from the function, but we are calculating the diameter in res variable... That res variable is passed by reference, that's why we will have the final answer in it when we return to main function. We are returning height, because we need left and right height to calculate diameter
dude it might be his general syntax, I accept it is redundant but not wrong , its his way of solving tree with this general syntax , might help later... :)
The second line in induction step is not required. You are taking max between (1+l+r) and temp, which is 1+max(l, r). So, the result will always be (1+l+r). Induction: # calculate current diameter dia = 1 + l + r # if the current diameter is greater than the previously computed diameters, update res = max(res, dia) # return the height to parent node return 1 + max(l, r)
Logic - Base Condition -> Stop when the node is null by returning 0. Main Logic -> You are supposed to find the max diameter at each node and update the variable which stores the max diameter found till that point, 'diameter' in the logic below. 1. At any node you can find the diameter by doing (1 + left + right), and then comparing if it is the max diameter till that point of time. If yes, store it in the 'diameter' variable. 2. Returning (1 + max(left,right)) to it's parent call to let parent node also calculate the diameter on similar lines as mentioned in step 1. Why max(left,right) ? As parent won't require both but just the path/height/depth that gives max value. In the end the 'diameter' variable would hold the answer. ------------------------------------------------------------------------------------- Java code - private static int diameter = Integer.MIN_VALUE; private static int getDiameter(Node node){ //Base condition if (node == null) return 0; //Main logic int left = getDiameter(node.left); int right = getDiameter(node.right); int diameterAtCurrentNode = 1 + left + right; diameter = Integer.max(diameter, diameterAtCurrentNode); return (1 + Integer.max(left,right)); }
I think left subtree and right subtree for any given node should return the depth and not diameter . The left subtree should return left depth and right subtree should return right depth . Then you can return 1+ max(leftdepth, right depth) which will contribute to the diameter in the case where the given node doesn't want to become the root of the diameter path. Bro, I think you should revise the video. It's not possible for left subtree to return left diameter since once you say DIAMETER you have already FIXED the end leaves. So no question of returning. Same goes for right subtree. Please follow the comment section where many people are addressing the same issue. Please address this issue and clear the confusion because I think your video on diameter is misleading students.
For those with doubtsaying max(l,r)+1 will always be < 1+l+r: This code works perfectly fine : int diautil(Node *n,int &res){ if(n==NULL)return 0; int l=diautil(n->left,res),r=diautil(n->right,res); res=max(l+r+1,res); return max(l,r)+1; }
root = 1, left = -1, right = -2.... 1 + -1+-2 = -2 and 1 + max(-1,-2) = 0....so in this case 1 + l +r is less than temp. But I think this can not be the answer as diameter is between two leaves, and in this case one node would not be the leaf so actually the statement is not only redundant but wrong! It would give wrong answer for test cases like I have shown you. Your code would be right then!! What do you think?
@@sakshigupta7616 But the left and right represents the no. of nodes in left subtree and right subtree, so the value of left and right can't be negative. Their minimum value can be zero if no nodes are present. (which is coming from our base condition).
True, but I think he's establishing a general format for the induction section so that it's easier to remember. See the next video where it becomes important to do the max of temp and result at current root.
The comment section is full of confusion but the explanation is correct. I've verified it by drawing the tree and traverse each and every node. If you have any issue, reply on this comment. I will try my best to explain!
Great video Bhaiya, just a correction, we can simply store (1+l+r) to the ans instead of storing max(temp,1+l+r) as (1+l+r) would always be greater than temp which is 1+max(l+r)
Aditya Verma: No, since diameter represent the number of nodes--> it selects the best among left and right (thats why max(l,r)) and then add one because of itself (counts itself) and then pass it further. I hope that clears your doubt. Thanks !!
Myself Charam (another comment I found useful) : To make things clear, the diameter of tree = max{ (lheight + rheight+1) for each and every node}. so our function actually returns the height of tree rooted at 'root'. res stores the max(lheight+rheight+1) and we traverse every node
Guys don't confuse height with diameter, height is no. of edges and diameter in this video is no of nodes. So, in any question they will tell what parameter we are to find and whether it is no of nodes or no of edges.
for Java Guys ... We As Java don't support Pass by reference.. So we need to create a new Class that is to be passed.. class Solution { // Function to return the diameter of a Binary Tree. class A{ int val=Integer.MIN_VALUE; } int diameter(Node root) { A res=new A(); solve(root,res); return res.val; } int solve(Node root, A res){ if(root==null){ return 0; } int l=solve(root.left,res); int r=solve(root.right,res); int temp=1+Math.max(l,r); int ans=Math.max(temp,1+r+l); res.val=Math.max(res.val,ans); return temp; } }
We can use single sized array or AtomicInteger, in case of AtomicInteger use set() method to set the value and while returning the value use get() method
my observations 1. diameter at any node is l+r+1 where l is height of left subtree and r is height of right subtree, 2. if i return height of node at any point would be sufficient what aditya teaching is complex res=max(res,l+r+1); return max(l,r)+1;
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
Solution of diameter of a tree using height helper function (as submitted on GFG): int height(Node* child) { if (child == nullptr) return 0; return 1+max(height(child->left), height(child->right)); }
int diameter(Node* root) { if (root == nullptr) { return 0; } int root_path = height(root->left) + height(root->right) + 1; int left_path = diameter(root->left); int right_path = diameter(root->right); return max(root_path, max(left_path, right_path)); } Hope it helps! Thank you Aditya sir for the amazing content that you put out for free! It really really helps.
In code condition to calculate "ans" is not required because its ans = Max(temp, (l+r+1)); but we know temp is temp = max(l,r) +1; which makes ans = Max(max(l,r)+1, l+r+1) so the "l+r+1" will always be max unless any one is negative, so unless questions considering weights we dont need the step.
Wouldn't l + r + 1 always be greater than max(l,r) + 1 ? I think the line "int ans = max(temp, 1 + l + r) is not required at all because of the fact i mentioned.
Sir , in hypothesis part , you are treating l and r as diameters but in induction part, you are treating l and r as heights . Please clear my confusion !
l and r are heights. At every node, in temp, we are storing the max height, which can be from either left or right. Then in variable named ans , we are storing the diameter possible taking current node as root. Then we are comparing the diameter with res and updating it ,in case the current answer is greater than res
@@yashrathore9427 1+max(l,r) gives diameter....please note: l and r are not the heights of left and right subtree.....instead they will give diameter of left subtree and right subtree respectively.
@@deepjyotsinghkapoor1955 l and r gives max height of left and right subtree, so temp is max height, as you can also see, we are returning res as our final diameter and not temp ( which is max height) got submitted on gfg
Exactly, mujhe wohi nhi samajh aa raha tha akhir ans=max(temp,1+l+r) karne ki kya zarurat hai, kyuki ans toh humesha 1+l+r hi hoga. temp toh kabhi 1+l+r se bada ho hi nhi sakta!
public static int fetchDiameter(TreeNode root) { if (root == null) { return 0; } int nodesInLeft = fetchDiameter(root.left); int nodesInRight = fetchDiameter(root.right); // If this node is not the actual root. // then we have to send to root, what is the max // number of nodes i can calculate from here. int temp = 1 + Math.max(nodesInLeft, nodesInRight); // Now let's check if this "node" can actually contribute // to the diameter. int answer = Math.max(temp, 1 + nodesInLeft + nodesInRight); // We have to check this at every node // since max diameter can go through any node in the tree. DIAMETER = Math.max(DIAMETER, answer); return temp; } Full Program on : github.com/neerajjain92/data-structures/blob/master/src/com/leetcode/year_2020/DP/dynamic_programming_on_trees/DiameterOfBinaryTree.java
this is the way for dp solution which u can use class Solution { public: pair diameterOfBinaryTre(TreeNode* root) { // base case if(root==NULL) { pair p; p.first =0; p.second=0; return p; } pair opt1= diameterOfBinaryTre(root->left ); pair opt2= diameterOfBinaryTre(root->right); int opt3=opt1.first+opt2.first; int height = max(opt1.first,opt2.first)+1; pair output; output.first=height; output.second=max(opt1.second,max(opt2.second,opt3)); return output; } int diameterOfBinaryTree(TreeNode* root) { return diameterOfBinaryTre(root).second; } };
Since there is no pass by reference in java, we can achieve the same by passing an array as follows - "class Solution { public int recursive(TreeNode root, int[] result){ if(root==null){ return 0; } int left_height=recursive(root.left,result); int right_height=recursive(root.right,result); int temp=Math.max(left_height,right_height)+1; int ans=Math.max(left_height+right_height+1,temp); result[0]=Math.max(result[0],ans); return temp; } public int diameterOfBinaryTree(TreeNode root) { int [] result=new int [1]; recursive(root,result); return result[0]-1; } }"
for those who are struggling on gfg:- int solve(Node* root,int &res) { if(root==nullptr) return 0; int l=solve(root->left,res); int r=solve(root->right,res); int height=1+max(l,r); res=max(res,1+l+r); return height; }
int diameter(Node* root) { if(!root) return 0; int res=INT_MIN; int x=solve(root,res); return res; }
Answer for the leet code question, in leetcode they ask for number of edges which does not include the starting node, whereas in this question in the video we are including the starting node as well, so to answer the leetcode question just subtract 1 from final result leetcode.com/problems/diameter-of-binary-tree/ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int result = Integer.MIN_VALUE; public int diameterOfBinaryTree(TreeNode root) { solve(root); return result-1; }
public int solve(TreeNode root) { if(root == null) { return 0; }
int left = solve(root.left); int right = solve(root.right);
int temp = 1 + Math.max(left, right); int ans = Math.max(temp, 1 + left + right);
Diameter of binary tree is : Max height of left node + Max height of right node + 1 (Current node itself) This will resolve the confusion as per why were are calculating Math.max(left,right)+1 in Temp variable. Although Answer variable is not really needed and added some confusion , Here is the simple code snippet private static int solve(Node root) { //Following two code blocks will always be fixed. if(root==null){ return 0; } int left = solve(root.left); int right = solve(root.right); //Calculating height of Node to retrieve the longest path int longestPathOfNode = Math.max(left,right)+1; //Update diameter when you find a bigger one diameter = Math.max(diameter,1+left+right); //Return the longest path which could be either left or right path for next calculation. return longestPathOfNode; } ^^ We are updating diameter when we find a bigger one that is all.
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; }
Dp is involved dude....How ? Each recursive call of subtree is returning a answer to top part of tree,it means that we are building the tree from bottom to top and the answers computed at the bottom are passsed to the top,Anyways it its not stored in seperate table since those temp and res are themselves getting updated in each call.
DP doesn't always means that you will need a data structure to store all the values for every level. If you can pass a calculated value from one level to another then also its kinda DP
Can you run this code on leetcode and pass all test cases ? It's not diameter...it's height. You can never add 1 to diameter since diameter already includes all nodes in the max path. Please post code link here.
return solve(*root,&res) if you want the #nodes in the longest path, and return solve(*root,&res)-1 if you need #edges in the longest path. Happy coding!!
The explanation could have been a little better.. Actually the function is returning the right of the tree and while finding the height of the tree for every node we are also considering the possibility that would would the diameter of the entire tree if the it passes through the node we are currently evaluating, we compare it with the diameters for nodes we have previously evaluated and store that if its greater. Finally after we have traversed the entire tree we end up with the diameter of the entire tree in our reference variable.
Sir aapne temp meh 1 add kr liya ...matlab parent ko include kr liya ...toh fr ans meh kyu krna h +1 ....jab parent ko max of left and right lete time he include kr rheh h
u can simply do this, BTW great tutorial loved it !! public int getMaxPathSumBT(TreeNode node) { if(node == null) return 0; int rightSum = getMaxPathSumBT(node.right); int leftSum = getMaxPathSumBT(node.left); int currentPathSum = node.val + Math.max(leftSum, rightSum); int currentMax = Math.max(currentPathSum, node.val + leftSum + rightSum); sum = Math.max(sum, currentMax); return currentPathSum; }
Java Code: class Solution { int maxValue = Integer.MIN_VALUE; public int diameterOfBinaryTree(TreeNode root) { height(root); return maxValue - 1; } private int height(TreeNode root) { if (root == null) return 0; int left = height(root.left); int right = height(root.right);
// Calculate the height of the current subtree rooted at 'root' int temp = 1 + Math.max(left, right);
// Calculate the potential diameter of the current subtree // rooted at 'root' (passing through 'root') int answer = Math.max(temp, 1 + left + right);
// Update 'maxValue' with the maximum diameter found so far maxValue = Math.max(maxValue, answer);
// Return 'temp' as the height of the current subtree rooted at 'root' return temp; } }
In some qs like in leetcode they ask diameter as no of edges instead of no of nodes so in that case just remember that ( no of edges =no of vertices -1) so return ans-1
@@gta6515 I literally searched for "leetcode" on the page just to see if I am the only one who had this problem while running the algo on leetcode and found your comment. :P. Thanks for explaining I also was not getting the right answer (Y)
Awesome explanation!!! One query though - In the induction step, if this node itself has the answer then it should just use "1+l+r", why should we consider max(temp, (1+l+r)). temp is to store what is this node's contribution to its ancestor when this node can't be the answer
temp is returned in the recursive function so that it keeps solving the subroutines to get the max value. Since res was passed by reference we don't have to return it.
How this topic will come under DP? isn't it just pure recursion? we are not storing and value to avoid calling same function, although we will not call same function in here it will be O(N) solution.
Hello Aditya, i think you are continuously using the word diameter instead of height in the video, the l and r variables are containing the height of the left and right sub-tree.
No, l and r are the diameter of the left subtree and right subtree and not heights, thats why I am continuously using the word diameter, because they are diameters 😅✌️
@@TheAdityaVerma Bro ,It's little confusing , when you don't want that particular node to be included in the diameter , then you are just calculating (1+max(l,r)). So,this means that you are taking the max. height that can contribute,how can this be diameter . Plz explain
say that V is the node and v1 is a child of V, now for v1 it returns temp to its parent ie V, we know temp is storing the result in which the diameter is not passing through v1, say v1 returns temp=5 to V, now ans for V say is 7 and so is the res, but problem is that what if the child v1's ans=9 ie the ans in which v1 is passing through the diameter, then in this case the final answer is 9 but we'll get 7 as for root node ie V we are returning ans to the main method..... please explain.
You are saying that hypothesis returns the diameter. Then how can you add 1 to Max(l, r). You should add 1 to the max height of left and right subtree, not the diameter.
No, since diameter represent the number of nodes--> it selects the best among left and right (thats why max(l,r)) and then add one because of itself (counts itself) and then pass it further. I hope that clears your doubt. Thanks !!
To make things clear, the diameter of tree = max{ (lheight + rheight+1) for each and every node}. so our function actually returns the height of tree rooted at 'root'. res stores the max(lheight+rheight+1) and we traverse every node
Hi Aditya! Awesome content.. this will be breaking the internet soon.. ! Just one point on this video.. the temp Value returned by the recursive functions should be the height.. and not the diameter. Diameter should only be used to update the result ..
There is a small mistake at 13:25. For the final answer, we have to return "res - 1" instead of "res" because we do not want to count the root node of the longest path. If you don't understand what I mean, try doing this question on LeetCode.
We will count for the root node But we want to calculate longest path which on leetcode mentioned as max number of edges between two nodes, that's why we need to return (res-1).
Sachme vaiya apke video dekhne k baad lagtai nahi dp ya recursion koi tough nahi he, lekin competive me halat thoda kharap ho jata he😢, uska kuch upai bolo na
this can be done w/o DP. First we need to traversal tree to find level of each leaf node. Second, select leaf at bottom most level(say X). Now using X as root traverse the tree keeping a counter variable(counter increments on each level). It will give answer.
@@kunalbabbar7399 Dp is involved. Each recursive call of subtree is returning a answer to top part of tree,it means that we are building the tree from bottom to top and the answers computed at the bottom are passsed to the top, But it its not stored in seperate table since those temp and res are themselves getting updated in each call.
543. The diameter of Binary tree (Leetcode) Followed the same method but we need to do a little change here. In the leetcode test cases, they are not considering the root as the part of the binary tree. Strange though. So wee have to just subtract -1 from the result. class Solution { int result=1; public int diameterOfBinaryTree(TreeNode root) {
This is because they are considering edges and number of edges in a tree are (number of nodes -1), while we are computing our answer based on nodes. So this is the reason we have to subtract 1 from our final result.
int left = find_diameter(root->left,result); int right = find_diameter(root->right,result);
int not_going_throught_it = max(left,right)+1; int going_throught_it = left+right; /*max(not_going_throught_it, 1+left+right);*/ result = max(result,going_throught_it);
return not_going_throught_it; } int diameterOfBinaryTree(TreeNode* root) { int result = INT_MIN; if(!root) return 0; find_diameter(root,result); return result; } };
The day this guy releases Graph, companies will have to change the way they interview
correct😃
Can you suggest some good graph series in hindi
nazar laga di na
@@livelypooja Striver Graph series is enough!
@@livelypooja have you completed graph ?
correction: just 'return res - 1' as question asked for number of edges not nodes. This code is right. Just do 'return' as per question statement.
thanks a lot , i am struggling with nodes
here actually l and r are returning the heights of the left and right subtrees, not the diameters. Coz the diameter of the whole tree is basically the maximum value of (l + r + 1) for every node, this is what being done here.
Yes absolutely
correct and thankyou
Correct
Correct
Exactly
Thanks Aditya for great video lists.
Diameter should be calculated as
int temp=max(l,r)+1;
res=max(1+l+r,res);
no need to calculate ans
can you give me the java solution
Yeah. max(temp, 1+l+r) is always going to be 1+l+r anyways.
Thanks... even I was confused during the explanation that why ans was calculated.
exactly because my diameter is alwaya lh +rh +1 in all cases so res=INT_MIN; then we can find out only matter of fact is I need the maximum left height for root left and maximum right height for roots right so my induction return type will be 1+max(lh,rh);
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int solve(TreeNode* root,int& ans ){
if(root==nullptr){
return 0;
}
int lh=solve(root->left,ans);
int rh=solve(root->right,ans);
int temp=1+max(lh,rh);
ans= max(ans,lh+rh+1);
return temp;
}
int diameterOfBinaryTree(TreeNode* root) {
int ans=INT_MIN;
solve(root,ans);
return ans-1;
}
};
True bruhhh
47 of 50 (94%) done! As others have mentioned comparing temp with 1+l+r is not reqd. Also, if we replace temp with what it truly is (height of cur node, max depth from cur node, etc.), then it would be clear. Similarly, ans = cur_dia
In this code the number of nodes are being counted but we need to find (depth of left tree + depth of right tree). In this code a correction needs to be done. We have to return res-1 to ensure that we are not counting the top node of diameter.
baki log to bs video dekh ke waah waah kie ja rhe...........khud se try kr ni rhe bs gyaan pele ja rhe comments me
@AdityaVerma please pin this comment
otherwise the solution is not submitting
Yes. In the leetcode question, they have specified they need the number of "edges" in the longest path, not the vertices. Number of edges in a tree = number of vertices(nodes) - 1 // basic stuff: 2 nodes are required to make 1 edge, 3 nodes required to make 2 edges and so on.
In the above approach what we are essentially calculating is the number of nodes, so in order to return the edge count, we simply reduce the answer by 1. Anyways, this is the best youtube channel to learn DP, period. Huge respect to Aditya. Below is the implementation of this solution in java. We don't need to pass "res" as a method arg, instead we can keep it as global variable
class Solution {
int finalAnswer = Integer.MIN_VALUE;
public int diameterOfBinaryTree(TreeNode root) {
func(root); // we don't need the output of this, as "finalAnswer" variable will have the answer
return finalAnswer-1; // finalAnswer is the number of nodes, we need to return # of edges, hence -1
}
int func(TreeNode node) {
if(node == null)
return 0;
int lsum = func(node.left);
int rsum = func(node.right);
int toUpperLevel = 1 + Math.max(lsum, rsum); // we need to return this to previous call stack
// we dont need to compare the lengths of paths going via current node or via parent node.
// 1+lsum+rsum will always have larger value than 1+Max(lsum, rsum)
.
finalAnswer = Math.max(finalAnswer, 1+lsum+rsum);
return toUpperLevel;
}
}
True, else we can update res as l+r instead of 1+l+r.
In a tree, by defn of tree, if there are n nodes, then there are n-1 edges, secondly any subtree in a tree is a tree. That means, the diameter subtree is a tree too, and you can easily switch between nodes/edges by using the n nodes, n-1 edges logic.
No matter from which video you start , you will end up starting from the first video😂
True 😁
thats what you call calculating from base case😂😂
Key thing : diameter at each node is defined by 1 + lh (height of left tree) + rh (height of right tree). Just calculate that at each node to get the maximum diameter.
Hence use the height method for binary tree and just add the line to calculate the diameter which gives the O(N) solution.
The lines marked with --> are the extra lines for the diameter calculation. Rest is the good old height calculation method.
Code :
--> int ans = Integer.MIN_VALUE;
int height(Node root){
if(root== null)
return 0;
int lh = height(root.left);
int rh = height(root.right);
--> ans = Math.max(ans, 1 + lh + rh);
reurn 1 + Math.max(lh, rh);
}
correct
Anuj bhaiya also taught this method! But I didn't realise that time that this is DP. I still can't believe that we are doing DP without memoisation or tabularisation. But I understand that maybe we are using storage plus recursion that's why its DP
complete code
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;
}
};
For those struggling with the leetcode questions.See Bhaiya is calculating the number of nodes and in leetcode you are asked number of edges so return res-1;
class Solution {
public:
int solve(TreeNode* root,int &res)
{
if(root==nullptr)
return 0;
int l=solve(root->left,res);
int r=solve(root->right,res);
int height=1+max(l,r);
res=max(res,1+l+r);
return height;
}
int diameterOfBinaryTree(TreeNode* root) {
if(!root)
return 0;
int res=INT_MIN;
int x=solve(root,res);
return res-1;
}
};
res or *res plz clarify
@@abhishekbajaj109Here in the caller function we pass res and in the called function we have &res .This is call by reference.The changes made in the res o the called function will be reflected in the res of the caller function.
thankyou so much bro for this information❤
Thnks bhai😊
Just change the way u r evaluating the diameter..
maxpath= max(maxpath, leftpath+ right path)
DP be like - Abe merako to andar le😂😂
for ans, why are you evaluating it as max(temp, 1+l+r). 1+l+r will always be greater than temp right?
ofcourse
Plus diameter is from leaf to leaf right. So I don't think we should compare temp as temp is only from some leaf (other from left or right) to the current node. So there is no sense to include this path because it is not from leaf to leaf. And of course your reason is logical.
For without including root node
exactly.. it will always be greater than or equal to temp
yess, But Understand the intuition of Aditya verma for his whole dp series he write one code and do little bit changes for further upcoming same pattern question
This is a pure recursive solution. Where we use DP in this question
we can convert this in dp easily .... if you have seen previous video's
bhai...kaha the tum... mai pareshan ho gaya tha ki ye dp kaise hua... yeh to recursion hua hai
waise hum node aur diameter ka map banake kar sakte hai dp me
How we use dp in it because we visit every node only one time so what is need of memoization because we never need to call visited node again??
In my knowledge this video is little misleading, actually dp problem tree can be LCA based queries on tree. Same we can use jump pointer to answer efficiently this concept known as binary lifting. Other problems also exist on same line
int ans = max(temp, 1+l+r) is not required , ans = 1+l+r will work
great video BTW
then what is the use of temp and what will be its use if it only returns height of the tree ??
@@kalagaarun9638 we are returning height from the function, but we are calculating the diameter in res variable... That res variable is passed by reference, that's why we will have the final answer in it when we return to main function.
We are returning height, because we need left and right height to calculate diameter
dude it might be his general syntax, I accept it is redundant but not wrong , its his way of solving tree with this general syntax , might help later... :)
@@codeit8320 Exactly
The second line in induction step is not required. You are taking max between (1+l+r) and temp, which is 1+max(l, r). So, the result will always be (1+l+r).
Induction:
# calculate current diameter
dia = 1 + l + r
# if the current diameter is greater than the previously computed diameters, update
res = max(res, dia)
# return the height to parent node
return 1 + max(l, r)
Yes you are right
Logic -
Base Condition -> Stop when the node is null by returning 0.
Main Logic -> You are supposed to find the max diameter at each node and update the variable which stores the max diameter found till that point, 'diameter' in the logic below.
1. At any node you can find the diameter by doing (1 + left + right), and then comparing if it is the max diameter till that point of time. If yes, store it in the 'diameter' variable.
2. Returning (1 + max(left,right)) to it's parent call to let parent node also calculate the diameter on similar lines as mentioned in step 1.
Why max(left,right) ? As parent won't require both but just the path/height/depth that gives max value.
In the end the 'diameter' variable would hold the answer.
-------------------------------------------------------------------------------------
Java code -
private static int diameter = Integer.MIN_VALUE;
private static int getDiameter(Node node){
//Base condition
if (node == null)
return 0;
//Main logic
int left = getDiameter(node.left);
int right = getDiameter(node.right);
int diameterAtCurrentNode = 1 + left + right;
diameter = Integer.max(diameter, diameterAtCurrentNode);
return (1 + Integer.max(left,right));
}
Best content 👍
Please make series on graph and hashing.
class Solution {
public int solve(TreeNode root,int maxt[]){
if(root==null) {
return 0;
}
int maxn=Integer.MIN_VALUE;
int l= solve(root.left,maxt);
int r= solve(root.right,maxt);
int pass= 1+l+r;
int notpass= 1+ Math.max(l,r); //height
maxn= Math.max(pass,notpass);
maxt[0]=Math.max(maxt[0],maxn);
return notpass;
}
public int diameterOfBinaryTree(TreeNode root) {
// int res=Integer.MIN_VALUE;
int maxt[]={Integer.MIN_VALUE};
solve(root,maxt);
return maxt[0]-1;
}
I think left subtree and right subtree for any given node should return the depth and not diameter . The left subtree should return left depth and right subtree should return right depth . Then you can return 1+ max(leftdepth, right depth) which will contribute to the diameter in the case where the given node doesn't want to become the root of the diameter path. Bro, I think you should revise the video. It's not possible for left subtree to return left diameter since once you say DIAMETER you have already FIXED the end leaves. So no question of returning. Same goes for right subtree. Please follow the comment section where many people are addressing the same issue. Please address this issue and clear the confusion because I think your video on diameter is misleading students.
True 🥲
Aditya bhai isme memoize nahi karenge kya ? Plz reply !
For those with doubtsaying max(l,r)+1 will always be < 1+l+r:
This code works perfectly fine :
int diautil(Node *n,int &res){
if(n==NULL)return 0;
int l=diautil(n->left,res),r=diautil(n->right,res);
res=max(l+r+1,res);
return max(l,r)+1;
}
root = 1, left = -1, right = -2.... 1 + -1+-2 = -2 and 1 + max(-1,-2) = 0....so in this case 1 + l +r is less than temp. But I think this can not be the answer as diameter is between two leaves, and in this case one node would not be the leaf so actually the statement is not only redundant but wrong! It would give wrong answer for test cases like I have shown you. Your code would be right then!! What do you think?
@@sakshigupta7616 But the left and right represents the no. of nodes in left subtree and right subtree, so the value of left and right can't be negative. Their minimum value can be zero if no nodes are present. (which is coming from our base condition).
bro value of temp always remain less than or equal to 1+r+l but why have we taken max(temp,1+r+l) as ans
comparing temp with 1+l+r is redundant. I have tried to solve the code without using this line and it worked. Simply store 1+l+r in ans.
True, but I think he's establishing a general format for the induction section so that it's easier to remember. See the next video where it becomes important to do the max of temp and result at current root.
Best solution of diameter of bt, thankyou!
why are we calling this dynamic programming tho?
I have the same doubt. Can anyone clarify??
Way better explanation than striver or Anuj bhaiya!
The comment section is full of confusion but the explanation is correct. I've verified it by drawing the tree and traverse each and every node. If you have any issue, reply on this comment. I will try my best to explain!
yeah the answer is correct.... but temp we re returning is height not the diameter .. i.e the value store in l,r are height not diameter.
Great video Bhaiya, just a correction, we can simply store (1+l+r) to the ans instead of storing max(temp,1+l+r) as (1+l+r) would always be greater than temp which is 1+max(l+r)
Temp is max of (l and r) + 1 and so temp will be less then or equal to l+r+1 always . Ans is simply l+r+1
Concept Understanding k liye lecture is perfect! Respect++;
// Correct Code
int solve(TreeNode* root, int &res)
{
if(root == NULL) return 0;
int l = solve(root->left, res);
int r = solve(root->right, res);
int temp = 1 + max(l,r);
res = max(res, l + r);
return temp;
}
At 6:05 you said "left diameter milega and right diameter milega" but I think you meant height , correct me if I'm wrong. Thanks
Aditya Verma: No, since diameter represent the number of nodes--> it selects the best among left and right (thats why max(l,r)) and then add one because of itself (counts itself) and then pass it further. I hope that clears your doubt. Thanks !!
Myself Charam (another comment I found useful) : To make things clear, the diameter of tree = max{ (lheight + rheight+1) for each and every node}.
so our function actually returns the height of tree rooted at 'root'.
res stores the max(lheight+rheight+1) and we traverse every node
He has power to give the exact words to every single possible doubt.
Guys don't confuse height with diameter, height is no. of edges and diameter in this video is no of nodes. So, in any question they will tell what parameter we are to find and whether it is no of nodes or no of edges.
bhai tujhe kisi ne pucha kyu gyan bat rha hai
I don't know why we are comparing *temp and (1+l+r)* in *ans* because (1+l+r) will always > temp...
{ temp= max(l,r) +1 }
can you make some more videos on trees? Your explanation is the best so far I have seen on any videos or text books
for Java Guys ... We As Java don't support Pass by reference.. So we need to create a new Class that is to be passed..
class Solution {
// Function to return the diameter of a Binary Tree.
class A{
int val=Integer.MIN_VALUE;
}
int diameter(Node root) {
A res=new A();
solve(root,res);
return res.val;
}
int solve(Node root, A res){
if(root==null){
return 0;
}
int l=solve(root.left,res);
int r=solve(root.right,res);
int temp=1+Math.max(l,r);
int ans=Math.max(temp,1+r+l);
res.val=Math.max(res.val,ans);
return temp;
}
}
Thanks man
@@ravishraj664 or we can pass 1 size array and store ans in it
We can use single sized array or AtomicInteger, in case of AtomicInteger use set() method to set the value and while returning the value use get() method
my observations
1. diameter at any node is l+r+1 where l is height of left subtree and r is height of right subtree,
2. if i return height of node at any point would be sufficient
what aditya teaching is complex
res=max(res,l+r+1);
return max(l,r)+1;
I agree. Couldn't visualise or understand it. He doesnt dry run the dp or recursive solution
can u please made a video on LIS , DP on grid , and kadane's algorithm
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@@TheAdityaVerma, As the June is going on can you please upload the remaining videos ASAP.
@@TheAdityaVerma 10 months later , we are still waiting
@@TheAdityaVerma 1 year later and we are still waiting
@@TheAdityaVerma it's may please upload ;)
why are we returning temp instead of res??
Thanks man🙏🙏 you have done really a great job for a student like me who think dp as nightmare .
How DP is used here? We are not storing any values or reusing the calculations done in previous recursion calls? is returning temp working here as DP?
Verma ji ne extra views k liye trees k problems ko dp ki playlist mei daal diya. Business karo toh bada karo Purshotam bhai
ans = 1+l+r
will also work here because temp is always going to be less
Solution of diameter of a tree using height helper function (as submitted on GFG):
int height(Node* child) {
if (child == nullptr)
return 0;
return 1+max(height(child->left), height(child->right));
}
int diameter(Node* root) {
if (root == nullptr) {
return 0;
}
int root_path = height(root->left) + height(root->right) + 1;
int left_path = diameter(root->left);
int right_path = diameter(root->right);
return max(root_path, max(left_path, right_path));
}
Hope it helps! Thank you Aditya sir for the amazing content that you put out for free! It really really helps.
I tried both recursive and recursive with memo (using maps).
The time taken by simple recursion - 0.3s, time taken with memo - 0.9s.
try for really large trees. then u will see difference.
@@swakal8868 solution accept ho gaya?
Where is the repeated work mate? Is the memo ever used? 😂😅
"Apan" mil kar seekhenge.. great content
Waah bhai....kahi pr bhi samaj nhi aa rha tha....ye video me mast samaj aa gaye
In code condition to calculate "ans" is not required because its
ans = Max(temp, (l+r+1));
but we know temp is
temp = max(l,r) +1;
which makes
ans = Max(max(l,r)+1, l+r+1)
so the "l+r+1" will always be max unless any one is negative,
so unless questions considering weights we dont need the step.
Wouldn't l + r + 1 always be greater than max(l,r) + 1 ? I think the line "int ans = max(temp, 1 + l + r) is not required at all because of the fact i mentioned.
Yes
Sir , in hypothesis part , you are treating l and r as diameters
but in induction part, you are treating l and r as heights .
Please clear my confusion !
l and r are heights. At every node, in temp, we are storing the max height, which can be from either left or right. Then in variable named ans , we are storing the diameter possible taking current node as root. Then we are comparing the diameter with res and updating it ,in case the current answer is greater than res
Excellent explaination. Just one question, the variable temp will store diameter or height?
Thanks priya !! It is storing the diameter.
@@TheAdityaVerma how ? 1+max(l, r) is height sir. I think ans variable is storing diameter.
@@TheAdityaVerma it should be the height
@@yashrathore9427 1+max(l,r) gives diameter....please note: l and r are not the heights of left and right subtree.....instead they will give diameter of left subtree and right subtree respectively.
@@deepjyotsinghkapoor1955 l and r gives max height of left and right subtree, so temp is max height, as you can also see, we are returning res as our final diameter and not temp ( which is max height)
got submitted on gfg
thanks sir for providing dp series
There is no dp used right? We are not storing data.
sir awesome explanation sir after every code you should also tell time complexity of that optimized code it will be a great help
Bhaiyya, we can do it in this way too
temp=1+max(l,r)
Int ans=1+l+r
res=max(res,ans)
return(temp)
Exactly, mujhe wohi nhi samajh aa raha tha akhir ans=max(temp,1+l+r) karne ki kya zarurat hai, kyuki ans toh humesha 1+l+r hi hoga. temp toh kabhi 1+l+r se bada ho hi nhi sakta!
@@mainaksanyal9515 yes 1+max(l,r)=0,r>=0 ;
public static int fetchDiameter(TreeNode root) {
if (root == null) {
return 0;
}
int nodesInLeft = fetchDiameter(root.left);
int nodesInRight = fetchDiameter(root.right);
// If this node is not the actual root.
// then we have to send to root, what is the max
// number of nodes i can calculate from here.
int temp = 1 + Math.max(nodesInLeft, nodesInRight);
// Now let's check if this "node" can actually contribute
// to the diameter.
int answer = Math.max(temp, 1 + nodesInLeft + nodesInRight);
// We have to check this at every node
// since max diameter can go through any node in the tree.
DIAMETER = Math.max(DIAMETER, answer);
return temp;
}
Full Program on : github.com/neerajjain92/data-structures/blob/master/src/com/leetcode/year_2020/DP/dynamic_programming_on_trees/DiameterOfBinaryTree.java
Why are we returning temp in the solve function...not res? as res holds the max value
this is the way for dp solution which u can use
class Solution {
public:
pair diameterOfBinaryTre(TreeNode* root) {
// base case
if(root==NULL)
{
pair p;
p.first =0;
p.second=0;
return p;
}
pair opt1= diameterOfBinaryTre(root->left );
pair opt2= diameterOfBinaryTre(root->right);
int opt3=opt1.first+opt2.first;
int height = max(opt1.first,opt2.first)+1;
pair output;
output.first=height;
output.second=max(opt1.second,max(opt2.second,opt3));
return output;
}
int diameterOfBinaryTree(TreeNode* root) {
return diameterOfBinaryTre(root).second;
}
};
Since there is no pass by reference in java, we can achieve the same by passing an array as follows -
"class Solution {
public int recursive(TreeNode root, int[] result){
if(root==null){
return 0;
}
int left_height=recursive(root.left,result);
int right_height=recursive(root.right,result);
int temp=Math.max(left_height,right_height)+1;
int ans=Math.max(left_height+right_height+1,temp);
result[0]=Math.max(result[0],ans);
return temp;
}
public int diameterOfBinaryTree(TreeNode root) {
int [] result=new int [1];
recursive(root,result);
return result[0]-1;
}
}"
for those who are struggling on gfg:-
int solve(Node* root,int &res)
{
if(root==nullptr)
return 0;
int l=solve(root->left,res);
int r=solve(root->right,res);
int height=1+max(l,r);
res=max(res,1+l+r);
return height;
}
int diameter(Node* root) {
if(!root)
return 0;
int res=INT_MIN;
int x=solve(root,res);
return res;
}
Amazing lecture
Answer for the leet code question, in leetcode they ask for number of edges which does not include the starting node, whereas in this question in the video we are including the starting node as well, so to answer the leetcode question just subtract 1 from final result
leetcode.com/problems/diameter-of-binary-tree/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution
{
int result = Integer.MIN_VALUE;
public int diameterOfBinaryTree(TreeNode root)
{
solve(root);
return result-1;
}
public int solve(TreeNode root)
{
if(root == null)
{
return 0;
}
int left = solve(root.left);
int right = solve(root.right);
int temp = 1 + Math.max(left, right);
int ans = Math.max(temp, 1 + left + right);
result = Math.max(result, ans);
return temp;
}
}
bruh -_-
How is it DP? we are not using any cache here...
Diameter of binary tree is : Max height of left node + Max height of right node + 1 (Current node itself)
This will resolve the confusion as per why were are calculating Math.max(left,right)+1 in Temp variable.
Although Answer variable is not really needed and added some confusion , Here is the simple code snippet
private static int solve(Node root) {
//Following two code blocks will always be fixed.
if(root==null){
return 0;
}
int left = solve(root.left);
int right = solve(root.right);
//Calculating height of Node to retrieve the longest path
int longestPathOfNode = Math.max(left,right)+1;
//Update diameter when you find a bigger one
diameter = Math.max(diameter,1+left+right);
//Return the longest path which could be either left or right path for next calculation.
return longestPathOfNode;
}
^^ We are updating diameter when we find a bigger one that is all.
Diameter will be passed as function argument right?
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;
}
Bhaiya 1+l+r to temp se hamesha bada hoga to usko i think redundant kar sakte
Woi mai bhi soch raha tha rather just res me max updation se ho jaega kaam i think
Sirf 1+l+r hee ans mein assign ker do .
Tum sai ho!!!
I don't understand one thing i,e where is DP used in it...this is normal recursive code??
yes i agree ! this is regular recursion no dp involved here!
Dp is involved dude....How ? Each recursive call of subtree is returning a answer to top part of tree,it means that we are building the tree from bottom to top and the answers computed at the bottom are passsed to the top,Anyways it its not stored in seperate table since those temp and res are themselves getting updated in each call.
DP doesn't always means that you will need a data structure to store all the values for every level. If you can pass a calculated value from one level to another then also its kinda DP
Plz make such vedios for graph and tree using recursion 🙏 @aditya
Can you run this code on leetcode and pass all test cases ? It's not diameter...it's height. You can never add 1 to diameter since diameter already includes all nodes in the max path. Please post code link here.
return solve(*root,&res) if you want the #nodes in the longest path, and return solve(*root,&res)-1 if you need #edges in the longest path. Happy coding!!
The explanation could have been a little better..
Actually the function is returning the right of the tree and while finding the height of the tree for every node we are also considering the possibility that would would the diameter of the entire tree if the it passes through the node we are currently evaluating, we compare it with the diameters for nodes we have previously evaluated and store that if its greater. Finally after we have traversed the entire tree we end up with the diameter of the entire tree in our reference variable.
Sir aapne temp meh 1 add kr liya ...matlab parent ko include kr liya ...toh fr ans meh kyu krna h +1 ....jab parent ko max of left and right lete time he include kr rheh h
can you please explain why we are returning ans or temp ans in tree questions (i mean why tempans here and ans in other questions)
u can simply do this, BTW great tutorial loved it !!
public int getMaxPathSumBT(TreeNode node) {
if(node == null) return 0;
int rightSum = getMaxPathSumBT(node.right);
int leftSum = getMaxPathSumBT(node.left);
int currentPathSum = node.val + Math.max(leftSum, rightSum);
int currentMax = Math.max(currentPathSum, node.val + leftSum + rightSum);
sum = Math.max(sum, currentMax);
return currentPathSum;
}
Java Code:
class Solution {
int maxValue = Integer.MIN_VALUE;
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return maxValue - 1;
}
private int height(TreeNode root) {
if (root == null) return 0;
int left = height(root.left);
int right = height(root.right);
// Calculate the height of the current subtree rooted at 'root'
int temp = 1 + Math.max(left, right);
// Calculate the potential diameter of the current subtree
// rooted at 'root' (passing through 'root')
int answer = Math.max(temp, 1 + left + right);
// Update 'maxValue' with the maximum diameter found so far
maxValue = Math.max(maxValue, answer);
// Return 'temp' as the height of the current subtree rooted at 'root'
return temp;
}
}
In some qs like in leetcode they ask diameter as no of edges instead of no of nodes so in that case just remember that ( no of edges =no of vertices -1) so return ans-1
Thank you so much for clearing.
@@gta6515 I literally searched for "leetcode" on the page just to see if I am the only one who had this problem while running the algo on leetcode and found your comment. :P.
Thanks for explaining I also was not getting the right answer (Y)
Can you explain pointer and reference in the middle of your video it won't take too much time please ...
I have some confusion on this topic
Please...
Awesome explanation!!!
One query though - In the induction step, if this node itself has the answer then it should just use "1+l+r", why should we consider max(temp, (1+l+r)). temp is to store what is this node's contribution to its ancestor when this node can't be the answer
yes
The diameter will be stored in res right. Then why are we returning temp in the function?
temp is returned in the recursive function so that it keeps solving the subroutines to get the max value. Since res was passed by reference we don't have to return it.
How this topic will come under DP? isn't it just pure recursion? we are not storing and value to avoid calling same function, although we will not call same function in here it will be O(N) solution.
Now i can find area of binary tree as well :P
How to minimize tree diameter by removing atmost k edges?
Hello Aditya, i think you are continuously using the word diameter instead of height in the video, the l and r variables are containing the height of the left and right sub-tree.
No, l and r are the diameter of the left subtree and right subtree and not heights, thats why I am continuously using the word diameter, because they are diameters 😅✌️
@@TheAdityaVerma Bro ,It's little confusing , when you don't want that particular node to be included in the diameter , then you are just calculating (1+max(l,r)). So,this means that you are taking the max. height that can contribute,how can this be diameter . Plz explain
@Prashant Tiwari Yes, we are correct . We should be returning heights and not diameter.
say that V is the node and v1 is a child of V, now for v1 it returns temp to its parent ie V, we know temp is storing the result in which the diameter is not passing through v1, say v1 returns temp=5 to V, now ans for V say is 7 and so is the res, but problem is that what if the child v1's ans=9 ie the ans in which v1 is passing through the diameter, then in this case the final answer is 9 but we'll get 7 as for root node ie V we are returning ans to the main method.....
please explain.
where is Dp in this approach ??
Why we return temp ; in recursive function?
Great explanation, but can we return res instead of temp?
Nope
No bro actual answer is not in temp but in res.temp is just returning height (not diameter) .with the help of temp we are calculating res.
You are saying that hypothesis returns the diameter. Then how can you add 1 to Max(l, r). You should add 1 to the max height of left and right subtree, not the diameter.
No, since diameter represent the number of nodes--> it selects the best among left and right (thats why max(l,r)) and then add one because of itself (counts itself) and then pass it further. I hope that clears your doubt. Thanks !!
To make things clear, the diameter of tree = max{ (lheight + rheight+1) for each and every node}.
so our function actually returns the height of tree rooted at 'root'.
res stores the max(lheight+rheight+1) and we traverse every node
Hi Aditya! Awesome content.. this will be breaking the internet soon.. !
Just one point on this video.. the temp Value returned by the recursive functions should be the height.. and not the diameter. Diameter should only be used to update the result ..
This should be height and not diameter
thanks for the video
should we use res or *res in recursive calls
Your content so good bro ..
how is this dp?
There is a small mistake at 13:25. For the final answer, we have to return "res - 1" instead of "res" because we do not want to count the root node of the longest path. If you don't understand what I mean, try doing this question on LeetCode.
We will count for the root node But we want to calculate longest path which on leetcode mentioned as max number of edges between two nodes, that's why we need to return (res-1).
Great explanation . Just wanted to ask why is this a DP question?
Sachme vaiya apke video dekhne k baad lagtai nahi dp ya recursion koi tough nahi he, lekin competive me halat thoda kharap ho jata he😢, uska kuch upai bolo na
Aditya Man....can you start series on Backtracking
this can be done w/o DP. First we need to traversal tree to find level of each leaf node. Second, select leaf at bottom most level(say X). Now using X as root traverse the tree keeping a counter variable(counter increments on each level). It will give answer.
Yes, we can do without dp by pre order traversal on tree
@@kunalbabbar7399 This, itself is preorder bro.
@@prinzuchoudhury6920 yes
@@prinzuchoudhury6920 but it's not looking like dp
@@kunalbabbar7399 Dp is involved. Each recursive call of subtree is returning a answer to top part of tree,it means that we are building the tree from bottom to top and the answers computed at the bottom are passsed to the top, But it its not stored in seperate table since those temp and res are themselves getting updated in each call.
Global variable bhi bana sakte hai
Where is dp in this?
which part is dp here?
since diamater will be non-negative ans will always be equal to 1 + l_d + r_d right? That step you can remove it ig
543. The diameter of Binary tree (Leetcode)
Followed the same method but we need to do a little change here. In the leetcode test cases, they are not considering the root as the part of the binary tree. Strange though. So wee have to just subtract -1 from the result.
class Solution {
int result=1;
public int diameterOfBinaryTree(TreeNode root) {
if(root==null) return 0;
solve(root);
return result-1;
}
public int solve(TreeNode root){
if(root==null) return 0;
int left=solve(root.left);
int right=solve(root.right);
int temp=1+ Math.max(left,right);
int ans=Math.max(temp,left+right+1);
result=Math.max(result,ans);
return temp;
}
}
This is because they are considering edges and number of edges in a tree are (number of nodes -1), while we are computing our answer based on nodes. So this is the reason we have to subtract 1 from our final result.
Correction _____-------______----- return res-1;
Am i the only one whose answer is coming wrong using this approach 🤔
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int find_diameter(TreeNode* root,int&result){
if(!root) return 0;
int left = find_diameter(root->left,result);
int right = find_diameter(root->right,result);
int not_going_throught_it = max(left,right)+1;
int going_throught_it = left+right; /*max(not_going_throught_it, 1+left+right);*/
result = max(result,going_throught_it);
return not_going_throught_it;
}
int diameterOfBinaryTree(TreeNode* root) {
int result = INT_MIN;
if(!root) return 0;
find_diameter(root,result);
return result;
}
};
you can add 1+left+right to count the number of nodes