Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79 The test cases have been updated, so the code might tle, use long 😅
If you are getting runtime error while submiting the same code on leetcode,no need to worry,just do a minute change in the code,just typecast the value of index while pushing in the queue.You may ask since we applied a trick to tackle the integer overflow here,yes we did,but through this method we just ensure that the index we push everytime just comes under INT_MAX,and index difference is always under singed 32 bit ,i.e at max below 2^32 as stated in question itself. At everytime we are pushing (2*index+1) or (2*index+2),so its not exactly twice,its getting more than that ,thats why we need to typecast with long long.Hope its clear now. Below my accepted code - class Solution { public: int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
queueq; q.push({root,0}); int ans=0; while(!q.empty()) { int size=q.size(); int mn=q.front().second; int first,last;
Bro ...one doubt ...........we are typecasting the value while pushing in queue.......but the queue we made is to store node* and int datatype. So, would the queue store long long datatype. The code is working fine. Just wanted to know the logic. Thanks.
max value of 2*curr+1 can never be more tha 6001 after subtracting the curr with the min value. bcoz at each level once you subtract the minimum value you have range something like [0 , 1, ..................size-1]. Since size lies in the range [1 , 3000] It should work fine.
I realised that (somehow) not every variable in our code needs to be long long: //(Only) This needs to be long long because it'll be multiplied with 2 long long currIndex = nodesQueue.front().second - minIndex; By doing this my code ran in 6ms on Leetcode _(Faster than 95% people)_
bro, i am also solving arsh's dsa sheet. I solve tree problems regularly. But, still am not able to get the logic of the problems (medium level). I almost look the solution of every problem on yt. Can you tell me how I can solve this issue? Thankyou
Hi Striver Love your work absolute hardwork and dedication. A small clarification. as curr_id is contant multiple for a single loop it will not create any issue if we substact with min or not or even we can substract any random number from q.front().first We can substract 1 just for our personal understanding and indexing nodes as 1,2,3... Ex: 1 / \ 2 3 / \ \ 4 5 6 case 1:substracting 1 stack = [ [1 ,1] ] first time -> left = 1 right = 1 m = max(0,right-left +1) = 1 stack = [ [ 2,1] , [3,2] ] 2nd time -> left = 1 right = 2 m = max(1,right-left +1) = 2 stack = [ [4,1] , [5,2] ,[6,4] ] 3r time- > left = 1 right = 4 m = max(2,right-left +1) = 4 case2:substracting 257 stack = [ [1 ,1] ] first time -> left = 1 right = 1 m = max(0,right-left +1) = 1 stack = [ [ 2,-511] , [3,-510] ] 2nd time -> left = -511 right = -510 m = max(1,right-left +1) = 2 stack = [ [4,-1535] , [5,-1534] ,[6,-1532] ] 3rd time -> left = -1535 right = -1532 m = max(2,right-left +1) = 4 NOTE: leftNode = (1-257)*2+1 = -511 rightNode = (1-257)*2+2 = -510 LeetCode : 662 class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int: stack = [[root,1]] m = 0 while len(stack)>0: n = len(stack) temp = [] left = 0 right = 0 for i in range(n): top = stack[i] if i == 0: left = top[1] if i == n-1: right = top[1] if top[0].left != None: temp.append([top[0].left,(top[1]-256)*2+1]) if top[0].right != None: temp.append([top[0].right,(top[1]-256)*2+2]) stack = temp m = max(m,right-left+1)
I don't know when did you ran the code or when leetcode updated test cases....it still throws overflow error.....I have raised PR in his repo....let's see when does he accept
@@nikhilnagrale I created this comment....try this too Your idea to prevent the overflow was great but you did one mistake.....it shouldn't be the minIndex which needs to be subtracted rather it should be the maxIndex at each level. Moreover we need not calculate first and last with comparisons for each node at a level rather first is index of left most node at the level and last is index of rightmost node at that level........more refined code is as below class Solution { public: int widthOfBinaryTree(TreeNode* root) { int size; //Let's suppose all the nodes are stored in array like we did in heap sort in 1 based indexing int minIndex,maxIndex,maxi = 1; queue qu;// qu.push(make_pair(root,0)); pair temp; while(!qu.empty()) { size = qu.size(); minIndex = qu.front().second;//min index at this level will be index of leftmost node at this level maxIndex = qu.back().second;//max index at this level will be index of rightmost node at this level while(size--) { temp = qu.front(); qu.pop(); if(temp.first->left) qu.push(make_pair(temp.first->left,2*(temp.second-maxIndex)));//index of left child is 2x(parent's index) {1 based indexing} if(temp.first->right) qu.push(make_pair(temp.first->right,2*(temp.second-maxIndex)+1));//index of right child is 2x(parent's index) + 1 {1 based indexing} } maxi = max(maxi,maxIndex-minIndex+1);//number of nodes between minIndex and maxIndex including both } return maxi;
In code studio they have excluded all the null nodes and then calculate the width....which we can get easily by level order traversal and storing the max size of queue....
same in gfg also. class Solution { // Function to get the maximum width of a binary tree. int getMaxWidth(Node root) { // Your code here Queue qu=new LinkedList(); if(root==null){ return 0; } qu.add(root); int length=1; while(!qu.isEmpty()){ int size=qu.size(); // for storing 1d arraylist and after completion of 1d arraylist we append this in 2d arraylist List sublist=new ArrayList(); for(int i=0;i
@@takeUforward can we apply level concept here like vertical level we can store for every node and return the difference between the max and min level from map the same concept that we applied in bottom view of a tree q?
@@fffooccc9801 No, we can't use that concept because multiple nodes can overlap on a line in the same level Try to dry run your approach on this test case [1,3,2,5,3,null,9] Correct answer is 4 for this case
hey could you please explain why didnt we need to change queue's datatype to long too? We are storing 2*curid in queue only so dont w need to make changes there?
code you might looking for, for overflow problem use long long int widthOfBinaryTree(TreeNode* root) { if(!root) return 0; queue q; q.push({root,0}); int ans = 1; while(!q.empty()){ int size = q.size(); ans = max(ans,q.back().second-q.front().second+1); for(int i=0; ileft) q.push({temp.first->left,index*2+1}); if(temp.first->right) q.push({temp.first->right,index*2+2}); } } return ans; }
When you cast (curr) to long long during the computation ((long long) curr * 2 + 1), the arithmetic operation is done in long long, which avoids overflow at that specific moment. Even though the result is eventually cast back to int (when stored in the queue), the key difference is that performing the multiplication in long long prevents the overflow from happening during the intermediate calculation. The overflow issue arises during the calculation itself rather than just storing the result, which is why handling the intermediate calculations in long long makes a significant difference. class Solution { public: int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
queueq; q.push({root,0}); int ans=0; while(!q.empty()) { int size=q.size(); int mn=q.front().second; int first,last;
Your idea to prevent the overflow was great but you did one mistake.....it shouldn't be the minIndex which needs to be subtracted rather it should be the maxIndex at each level. Moreover we need not calculate first and last with comparisons for each node at a level rather first is index of left most node at the level and last is index of rightmost node at that level........more refined code is as below class Solution { public: int widthOfBinaryTree(TreeNode* root) { int size; //Let's suppose all the nodes are stored in array like we did in heap sort in 1 based indexing int minIndex,maxIndex,maxi = 1; queue qu;// qu.push(make_pair(root,0)); pair temp; while(!qu.empty()) { size = qu.size(); minIndex = qu.front().second;//min index at this level will be index of leftmost node at this level maxIndex = qu.back().second;//max index at this level will be index of rightmost node at this level while(size--) { temp = qu.front(); qu.pop(); if(temp.first->left) qu.push(make_pair(temp.first->left,2*(temp.second-maxIndex)));//index of left child is 2x(parent's index) {1 based indexing} if(temp.first->right) qu.push(make_pair(temp.first->right,2*(temp.second-maxIndex)+1));//index of right child is 2x(parent's index) + 1 {1 based indexing} } maxi = max(maxi,maxIndex-minIndex+1);//number of nodes between minIndex and maxIndex including both } return maxi;
So there is nothing wrong with subtracting either max or min, the only reason why this solution worked is because negative integers have one extra number. I used unsigned int and subtracted min and it worked perfectly. In the hindsight, unsigned int will give me same positive range as a long long int's positive range.
@@divyanshpant5318 Just think intuitively....if you wish to protect against overflow by going on a relative scale....then what will be more protective-> Subtracting smallest value from all values or subtracting largest value from all?
@@shwetanknaveen Here when u subtract largest element, all the indices will be negative. I confirmed this by printing the values. So rather than going from say 1 to 8 index values, largest element subtraction will iterate from 0 to -8, which in itself can equally likely lead to the possibility of overflow
Loved it, such a beautiful question that explored the concept of serialization. In the latest it seems leetcode has added a few more testcases, so this particular solution won't pass the newly added test cases and may give an error. So make sure either you use an unsigned long long to store serials/ids. Or otherwise you can do another hack that is to, instead of subtracting the max Serial/id for a particular level you can simply subtract max Id, it'll serialize the number in -ve and -ve range has one extra space than the positive range, hence it'll work.
I realised that (somehow) not every variable in our code needs to be long long: //(Only) This needs to be long long because it'll be multiplied with 2 long long currIndex = nodesQueue.front().second - minIndex; By doing this my code ran in 6ms on Leetcode _(Faster than 95% people)_
Bro instead of using 2*i+1,2*i+2 for 0 based index, we can use 2*i , 2*i +1 because this is same as taking minimal element in the level and subtracting.
Yeah it's really confusing nobody has explained it really but here is why it IS NOT the same - with 2*i , 2*i + 1 u might not always get your 1ST node at each level as 0 (Try it on a right skewed Tree) But with the explained method you will ALWAYS get your 1st node at each level as 0.
Apart from what is explained there is much to self analyze in this question , its okay if u spent an evening on it. (and that runtime is an analysis and also why min is not always 1 u will get this one via dry run for runtime wala thing just analyze the failed testcase and use gpt yes it will take sometime u need to think what happens when levels are increased exponentially (2^n) hope I helped u a little..
I have a doubt at 21:08 where you explain why the minimal index will change. if we were to change the minimal, suppose mini_ind = 2. now if we subtract to get the cur_id = (2-2 = 0) and then when I try getting the child's index it would go back to either 1 or 2 instead of 3 and 4 as 1 and 2 practically should be assigned to NULL (the left node of index 1 did not exist thus null values!) please explain
You do not need to actively check for the first and last indices at a particular level At a particular level the first index is at the top of the queue to be processed and the last index is at the end of the queue, curr points to the last index at the end of the traversal def widthOfBinaryTree(self, root): q=deque() curr=root width=0 q.append((curr,0)) while q: n=len(q) top,top_idx=q[0] for i in range(n): curr,curr_idx=q.popleft() if curr.left: q.append((curr.left,2*curr_idx)) if curr.right: q.append((curr.right,2*curr_idx+1)) width=max(width,curr_idx-top_idx+1)
I modified the formula to 2*node and 2*node+1 This works well on leetcode Besides none of those long long issues that are being pointed to in the comments class Solution { private class Pair{ int idx; TreeNode node; Pair(int idx, TreeNode node){ this.idx=idx; this.node=node; } } public int widthOfBinaryTree(TreeNode root) { Queue q=new LinkedList(); Pair temp; int width=0, begin, end, size; q.add(new Pair(0, root)); while(!q.isEmpty()){ size=q.size(); temp=q.poll(); begin=temp.idx; end=temp.idx; if(temp.node.left!=null){ q.add(new Pair(2*end, temp.node.left)); } if(temp.node.right!=null){ q.add(new Pair((2*end)+1, temp.node.right)); } for(int i=2;iwidth){ width=end-begin+1; } } return width; } }
Instead of taking values of the next nodes as (2*i+1) and (2*i+2), we can take (2*i) and (2*i+1), in this case, it is not required to subtract the minimum of nodes on the same level.
If anyone face issue of overflow just a bit change where we subtract min index we have to subtract the max index of current level where we store negative value as index for long width which solve the overflow issue. Below is the code of it. int widthOfBinaryTree(TreeNode* root) { if(root==NULL) return 0; queueq; q.push({root,0}); int res=0; while(q.empty()==false) { int start=q.front().second; int end=q.back().second; res=max(res,end-start+1); int size=q.size(); for(int i=0;ileft!=NULL) q.push({x.first->left,2*index+1}); if(x.first->right!=NULL) q.push({x.first->right,2*index+2}); } } return res; }
I we have level, we can say that maximum number of nodes in that level is 2^(level number) So we can simply find number of level, and use above formula
Python code: class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int: q=[(root,0)] ans=0 while q: n=len(q) mn=q[0][1] for i in range(n): curr=q[0][1]-mn node=q[0][0] q.pop(0) if i==0: first=curr if i==n-1: last=curr if node.left: q.append((node.left,2*curr+1)) if node.right: q.append((node.right,2*curr+2)) ans=max(ans,last-first+1) return ans
@Ayush Negi hey like but we never go to 2^3000 . i mean we always subtract the minimal from the indexing so at worst case of 3000 nodes we should be having number froms [0......3001] say. if i am wrong do reply. thanks
Hey thanks for the series, loving it. One doubt though : if what you mention is actually the width of the binary tree then couldn't you simply find this out using a formula? 2^n ?
if(node->left){ q.push({node->left, idx*2LL+1}); } if(node->right){ q.push({node->right, idx*2LL+2}); } do this on Line 31 and 33 instead before pushing it to the stack, that will fix the overflow!!!
think for 10-15 min about the approach and then see the video. Here you are learning about the concept of binary tree not practicing the questions. After learning the basic concept you can go to leetcode to solve different problems on tree. I hope it will help you.
Hello @take U forward can we just not calculate the depth of the of the tree and then do 2^(depth-1) ? It is working for all the cases I thought of Please let me know if I am thinking in the right direction or not .
Works by just writing long long in queue index class Solution { public: int widthOfBinaryTree(TreeNode* root) { if (root == NULL) { return 0; } int ans = 0; queue q; q.push({root, 0}); while (!q.empty()) { int size = q.size(); int first, last; for (int i = 0; i < size; i++) { int cur_id = q.front().second; TreeNode* node = q.front().first; q.pop(); if (i == 0) first = cur_id; if (i == size - 1) last = cur_id; if (node->left) { q.push({node->left, (long long)2 * cur_id + 1}); } if (node->right) { q.push({node->right, (long long)2 * cur_id + 2}); } } ans = max(ans, last - first + 1); } return ans; } };
Personal note: Why we are not subtracting 1 at every level from the index instead taking minimum from queue? coz it mignt happen only right subtree exists at a level
Doubt: In GFG, maximum width is defined as maximum nodes present in a particular level. In Leetcode: maximum width is the distance between 2 corner nodes in a level(including nulls). Can you confirm that GFG article is false or not?
Couldn't it also be done in the following way : I traverse to the left most leaf and store the level as lev1. Then, I traverse to the right most leaf and store the level as lev2. I get the minLevel = min(lev1, lev2) Max width = 2^(minLevel). Levels start from 0 index.
why cant we use the concept of "vertical indexing" which we use on top view of binary tree. by using this, we can take the first and last element and find the answer can anyone answer my question?
Width is calculated between any two nodes as explained initially we ignored the node in second tree in the beginning of the video How will skew tree with single line nodes can even be a possible test case ?
From code we can definitely say value of first is going to be zero. So, we only need to store value of last. Hence, ans = max(ans, last + 1) In face without even storing we can solve this. Follow below code.
Can you please clarify my doubt. imagine there are 3 levels in a tree. first and second levels are completely filled (1 root, 2 (root's left child), 3(roots right child) but the third level has starting node( 4, (2's left child) ) and (5, (3's left child)). what should be the solution to the above case, your program is giving 3 as the answer. but should the answer be 2 or 4 or 3 ?
This code is giving wrong answer at 101/114 test case. Can anybody pointout possible mistakes in it? int widthOfBinaryTree(TreeNode* root) { long long int ans = 1, c = 1; queueq, q2; q.push(root); while(q.size()) { int k = q.size(); vectorv; for(int i = 0; ileft) { q.push(a->left); v.push_back(a->left->val); } else v.push_back(-101); if(a->right) { q.push(a->right); v.push_back(a->right->val); } else v.push_back(-101); } if(!q.size()) break; c *= 2; long long i = 0, j = v.size()-1; while(i=i && v[j] == -101) {j--; c--;} ans = max(ans, c); } return ans; }
class Solution { public: int widthOfBinaryTree(TreeNode* root) { if (!root) return 0; int ans=0; queueq; q.push({root,0}); while(!q.empty()){ int size=q.size(); int min=q.front().second; int first,last; for(int i=0; ileft) q.push({node->left,cur_id*2+1}); if(node->right) q.push({node->right,cur_id*2+2});
Nice one but I guess it could be made even more simpler if you would have used the concept of vertical level as then you will be just subracting the vertical level of the last node and the first node of a particular horizontal level.
C++ Leetcode accepted Solution : class Solution { public: int widthOfBinaryTree(TreeNode* root) { if(!root) return 0; int ans=0; queue q; q.push({root, 0}); while(!q.empty()){ int size = q.size(); int mmin = q.front().second; // to take the id starting from zero int first, last; for(int i=0; ileft) q.push({node->left, cur_id*2+1}); if(node->right) q.push({node->right, cur_id*2+2}); } ans = max(ans, last-first+1); } return ans;
/** * 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 widthOfBinaryTree(TreeNode* root) { if(!root) return 0; int ans=0; queue pendingNodes;//int refers to the index number of the node...in a level the nodes always have index number ranging from (1...size of level) //any level starts from 1 or 2 and the index of the first node present in that level. //in practice the nodes which exist will have range from like 2000....something pendingNodes.push({root,0}); while(!pendingNodes.empty()){ int size=pendingNodes.size(); int minimum=pendingNodes.front().second; int first,last; for(int i=0;ileft) pendingNodes.push({node->left,(long long)2*cur+1});//when 2*cur+1 is calculated then the answer is an integer by default as 2,cur,1 aa are integers....but the result circumpassess the int_max limit...so it has to be manually typecasted to long long if(node->right) pendingNodes.push({node->right,(long long)2*cur+2}); } //one level processed ans=max(ans,last-first+1); } return ans; } };
It might be possible that the max depth might not have the maxwidth at all. In a case where at the max depth/lowest level might have only one node or even if it had 2 nodes the number of nodes in between those two nodes might be lesser than some thing we got at a level above the max depth. Thus max depth * 2 would become wrong in such cases.
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
The test cases have been updated, so the code might tle, use long 😅
It is not giving TLE but giving Runtime error which gets solved by a Long long .. Thank You so much bhaiyya for this Amazing series !!!!
@@Sumeet_100 u can use unsigned int in that everything goes fine with that
ThankGod someone updated!! I have been hitting my head for last 2hours.. finally saw this comment.. thanks.
If you are getting runtime error while submiting the same code on leetcode,no need to worry,just do a minute change in the code,just typecast the value of index while pushing in the queue.You may ask since we applied a trick to tackle the integer overflow here,yes we did,but through this method we just ensure that the index we push everytime just comes under INT_MAX,and index difference is always under singed 32 bit ,i.e at max below 2^32 as stated in question itself. At everytime we are pushing (2*index+1) or (2*index+2),so its not exactly twice,its getting more than that ,thats why we need to typecast with long long.Hope its clear now.
Below my accepted code -
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
queueq;
q.push({root,0});
int ans=0;
while(!q.empty())
{
int size=q.size();
int mn=q.front().second;
int first,last;
for(int i=0;ileft)
q.push({node->left,(long long)curr*2+1});
if(node->right)
q.push({node->right,(long long)curr*2+2});
}
ans=max(ans,last-first+1);
}
return ans;
}
};
Bro ...one doubt ...........we are typecasting the value while pushing in queue.......but the queue we made is to store node* and int datatype. So, would the queue store long long datatype. The code is working fine. Just wanted to know the logic. Thanks.
max value of 2*curr+1 can never be more tha 6001 after subtracting the curr with the min value.
bcoz at each level once you subtract the minimum value you have range something like [0 , 1, ..................size-1]. Since size lies in the range [1 , 3000] It should work fine.
I realised that (somehow) not every variable in our code needs to be long long:
//(Only) This needs to be long long because it'll be multiplied with 2
long long currIndex = nodesQueue.front().second - minIndex;
By doing this my code ran in 6ms on Leetcode _(Faster than 95% people)_
@@namansharma7328 Exactly, I had the same doubt...but magically it's working 😅
@Ayush Negi Mindblowing explanation! Thanks 🙏
This one was a thinker! I've solved 50+ trees problems now, but it took me more than an hour to solve this one on my own. Good one!
bro, i am also solving arsh's dsa sheet. I solve tree problems regularly. But, still am not able to get the logic of the problems (medium level). I almost look the solution of every problem on yt. Can you tell me how I can solve this issue?
Thankyou
@@siddhantrawat1588 just keep practicing and revising bro.. literally no other way!
Revise everyday to make sure you don't forget anything.
@@fanigo138 ok bro, thanks a lot
@@siddhantrawat1588 try to solve first more easy then move to medium
@@preetkatiyar969 ok, thank you
Hi Striver Love your work
absolute hardwork and dedication.
A small clarification.
as curr_id is contant multiple for a single loop it will not create any issue if we substact with min or not or even we can substract any random number from q.front().first
We can substract 1 just for our personal understanding and indexing nodes as 1,2,3...
Ex:
1
/ \
2 3
/ \ \
4 5 6
case 1:substracting 1
stack = [ [1 ,1] ] first time -> left = 1 right = 1 m = max(0,right-left +1) = 1
stack = [ [ 2,1] , [3,2] ] 2nd time -> left = 1 right = 2 m = max(1,right-left +1) = 2
stack = [ [4,1] , [5,2] ,[6,4] ] 3r time- > left = 1 right = 4 m = max(2,right-left +1) = 4
case2:substracting 257
stack = [ [1 ,1] ] first time -> left = 1 right = 1 m = max(0,right-left +1) = 1
stack = [ [ 2,-511] , [3,-510] ] 2nd time -> left = -511 right = -510 m = max(1,right-left +1) = 2
stack = [ [4,-1535] , [5,-1534] ,[6,-1532] ] 3rd time -> left = -1535 right = -1532 m = max(2,right-left +1) = 4
NOTE:
leftNode = (1-257)*2+1 = -511
rightNode = (1-257)*2+2 = -510
LeetCode : 662
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
stack = [[root,1]]
m = 0
while len(stack)>0:
n = len(stack)
temp = []
left = 0
right = 0
for i in range(n):
top = stack[i]
if i == 0:
left = top[1]
if i == n-1:
right = top[1]
if top[0].left != None:
temp.append([top[0].left,(top[1]-256)*2+1])
if top[0].right != None:
temp.append([top[0].right,(top[1]-256)*2+2])
stack = temp
m = max(m,right-left+1)
return m
Idea of handling Overflow was amazing!!!!! I solved that using unsigned long long LOL 😂😂
I don't know when did you ran the code or when leetcode updated test cases....it still throws overflow error.....I have raised PR in his repo....let's see when does he accept
@@shwetanknaveen I checked it right now it worked
@@shwetanknaveen but bhaiya method is better try to understand that
@@nikhilnagrale are you trying his code on git on leetcode?
@@nikhilnagrale I created this comment....try this too
Your idea to prevent the overflow was great but you did one mistake.....it shouldn't be the minIndex which needs to be subtracted rather it should be the maxIndex at each level. Moreover we need not calculate first and last with comparisons for each node at a level rather first is index of left most node at the level and last is index of rightmost node at that level........more refined code is as below
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
int size;
//Let's suppose all the nodes are stored in array like we did in heap sort in 1 based indexing
int minIndex,maxIndex,maxi = 1;
queue qu;//
qu.push(make_pair(root,0));
pair temp;
while(!qu.empty())
{
size = qu.size();
minIndex = qu.front().second;//min index at this level will be index of leftmost node at this level
maxIndex = qu.back().second;//max index at this level will be index of rightmost node at this level
while(size--)
{
temp = qu.front();
qu.pop();
if(temp.first->left) qu.push(make_pair(temp.first->left,2*(temp.second-maxIndex)));//index of left child is 2x(parent's index) {1 based indexing}
if(temp.first->right) qu.push(make_pair(temp.first->right,2*(temp.second-maxIndex)+1));//index of right child is 2x(parent's index) + 1 {1 based indexing}
}
maxi = max(maxi,maxIndex-minIndex+1);//number of nodes between minIndex and maxIndex including both
}
return maxi;
}
};
That intro music though😍😍😍😍😍 i skip relevel part and start from there...kudos to the one who created it
In code studio they have excluded all the null nodes and then calculate the width....which we can get easily by level order traversal and storing the max size of queue....
same in gfg also.
class Solution {
// Function to get the maximum width of a binary tree.
int getMaxWidth(Node root) {
// Your code here
Queue qu=new LinkedList();
if(root==null){
return 0;
}
qu.add(root);
int length=1;
while(!qu.isEmpty()){
int size=qu.size();
// for storing 1d arraylist and after completion of 1d arraylist we append this in 2d arraylist
List sublist=new ArrayList();
for(int i=0;i
awesome explanation! I earlier added this question to my doubt list but after watching this video my doubt is completely gone
Hi striver. You are working very hard for us and you please take rest . Health is also important.
yeah will go off once this tree series is done!
@@takeUforward theek hote hi Dp shuru 🙏
@@deepakojha8431 😄😄😄😄😄
@@takeUforward can we apply level concept here like vertical level we can store for every node and return the difference between the max and min level from map the same concept that we applied in bottom view of a tree q?
@@fffooccc9801 No, we can't use that concept because multiple nodes can overlap on a line in the same level
Try to dry run your approach on this test case
[1,3,2,5,3,null,9]
Correct answer is 4 for this case
They added 2 new test cases on Leetcode making the above code fail due to integer overflow. I had to use long long even after subtracting mmin
Me also bro
Exactly
Just make you integer unsigned, those also will pass.
@@theanmolmalik Hare Krishna! Thanks
@@rohitrautela6679 Greetings Karne ka Tarika h Prabhu Ji
ex Hi, Hello, like that
Hare Krishna! Rohit Ji.
Simplest Approach ⬇⬇⬇⬇⬇
int maxWidth(TreeNode *root) {
int ans,i=-1,j=-1;
TreeNode *node=root;
while(node!=NULL) {
i++;
node=node->left;
}
node=root;
while(node!=NULL) {
j++;
node=node->right;
}
ans=i
Try this test case : [1,3,2,5,null,null,9,6,null,7] ...output should be 7
to prevent the overflow condition for this code you can use "long" in line 25 instead of int. :)
hey could you please explain why didnt we need to change queue's datatype to long too?
We are storing 2*curid in queue only so dont w need to make changes there?
@@mahima1219 by the time it gets stored in there it has already been reduced fit into 32 bit i.e., an int
It worked !
Thanks bro
@@jeevan999able then why was it giving error while calculating, it is also 32 bit
code you might looking for, for overflow problem use long long
int widthOfBinaryTree(TreeNode* root) {
if(!root)
return 0;
queue q;
q.push({root,0});
int ans = 1;
while(!q.empty()){
int size = q.size();
ans = max(ans,q.back().second-q.front().second+1);
for(int i=0; ileft) q.push({temp.first->left,index*2+1});
if(temp.first->right) q.push({temp.first->right,index*2+2});
}
}
return ans;
}
You are pushing a long long into an int type queue, doesn't that give runtime error
When you cast (curr) to long long during the computation ((long long) curr * 2 + 1), the arithmetic operation is done in long long, which avoids overflow at that specific moment. Even though the result is eventually cast back to int (when stored in the queue), the key difference is that performing the multiplication in long long prevents the overflow from happening during the intermediate calculation. The overflow issue arises during the calculation itself rather than just storing the result, which is why handling the intermediate calculations in long long makes a significant difference.
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
queueq;
q.push({root,0});
int ans=0;
while(!q.empty())
{
int size=q.size();
int mn=q.front().second;
int first,last;
for(int i=0;ileft)
q.push({node->left,(long long)curr*2+1});
if(node->right)
q.push({node->right,(long long)curr*2+2});
}
ans=max(ans,last-first+1);
}
return ans;
}
};
Your idea to prevent the overflow was great but you did one mistake.....it shouldn't be the minIndex which needs to be subtracted rather it should be the maxIndex at each level. Moreover we need not calculate first and last with comparisons for each node at a level rather first is index of left most node at the level and last is index of rightmost node at that level........more refined code is as below
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
int size;
//Let's suppose all the nodes are stored in array like we did in heap sort in 1 based indexing
int minIndex,maxIndex,maxi = 1;
queue qu;//
qu.push(make_pair(root,0));
pair temp;
while(!qu.empty())
{
size = qu.size();
minIndex = qu.front().second;//min index at this level will be index of leftmost node at this level
maxIndex = qu.back().second;//max index at this level will be index of rightmost node at this level
while(size--)
{
temp = qu.front();
qu.pop();
if(temp.first->left) qu.push(make_pair(temp.first->left,2*(temp.second-maxIndex)));//index of left child is 2x(parent's index) {1 based indexing}
if(temp.first->right) qu.push(make_pair(temp.first->right,2*(temp.second-maxIndex)+1));//index of right child is 2x(parent's index) + 1 {1 based indexing}
}
maxi = max(maxi,maxIndex-minIndex+1);//number of nodes between minIndex and maxIndex including both
}
return maxi;
}
};
Thank you for the explanation!
@@sumedhvichare1388 glad it helped 👍
So there is nothing wrong with subtracting either max or min, the only reason why this solution worked is because negative integers have one extra number. I used unsigned int and subtracted min and it worked perfectly. In the hindsight, unsigned int will give me same positive range as a long long int's positive range.
@@divyanshpant5318 Just think intuitively....if you wish to protect against overflow by going on a relative scale....then what will be more protective-> Subtracting smallest value from all values or subtracting largest value from all?
@@shwetanknaveen Here when u subtract largest element, all the indices will be negative. I confirmed this by printing the values. So rather than going from say 1 to 8 index values, largest element subtraction will iterate from 0 to -8, which in itself can equally likely lead to the possibility of overflow
Loved it, such a beautiful question that explored the concept of serialization. In the latest it seems leetcode has added a few more testcases, so this particular solution won't pass the newly added test cases and may give an error. So make sure either you use an unsigned long long to store serials/ids. Or otherwise you can do another hack that is to, instead of subtracting the max Serial/id for a particular level you can simply subtract max Id, it'll serialize the number in -ve and -ve range has one extra space than the positive range, hence it'll work.
Thanks buddy !!!! both ideas worked
I realised that (somehow) not every variable in our code needs to be long long:
//(Only) This needs to be long long because it'll be multiplied with 2
long long currIndex = nodesQueue.front().second - minIndex;
By doing this my code ran in 6ms on Leetcode _(Faster than 95% people)_
Thank you, I was stuck and changing to long long made everything work.
Bro instead of using 2*i+1,2*i+2 for 0 based index, we can use 2*i , 2*i +1 because this is same as taking minimal element in the level and subtracting.
Yeah it's really confusing nobody has explained it really but here is why it IS NOT the same -
with 2*i , 2*i + 1 u might not always get your 1ST node at each level as 0 (Try it on a right skewed Tree)
But with the explained method you will ALWAYS get your 1st node at each level as 0.
Bro one suggestion , could u pls show a queue horizontally pls bro pls 🙏🙏👍👍 just helps in better visualization i think 😃
I can totally feel and understand you request.
it doesn't really matter
Assume queue to be a hollow pipe placed vertically.
I agree... many times i got confused his queue with stack while dry run
@@amanbhadani8840 yep that surely does help now that I think of it dude !
Apart from what is explained there is much to self analyze in this question , its okay if u spent an evening on it. (and that runtime is an analysis and also why min is not always 1 u will get this one via dry run for runtime wala thing just analyze the failed testcase and use gpt yes it will take sometime u need to think what happens when levels are increased exponentially (2^n) hope I helped u a little..
Kya hi mehnat kiye hai bhaiya iss video par
bhai aap living legend ho
humanity needs more people like you
You have to use long long even after this trick of saving integer overflow, using int gives runtime error.
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Hats off to you Striver! The way youve explained such a complex approach with so ease just makes me wonder how good your Intuition is.
I have a doubt at 21:08 where you explain why the minimal index will change. if we were to change the minimal, suppose mini_ind = 2. now if we subtract to get the cur_id = (2-2 = 0) and then when I try getting the child's index it would go back to either 1 or 2 instead of 3 and 4 as 1 and 2 practically should be assigned to NULL (the left node of index 1 did not exist thus null values!) please explain
You do not need to actively check for the first and last indices at a particular level
At a particular level the first index is at the top of the queue to be processed and the last index is at the end of the queue, curr points to the last index at the end of the traversal
def widthOfBinaryTree(self, root):
q=deque()
curr=root
width=0
q.append((curr,0))
while q:
n=len(q)
top,top_idx=q[0]
for i in range(n):
curr,curr_idx=q.popleft()
if curr.left:
q.append((curr.left,2*curr_idx))
if curr.right:
q.append((curr.right,2*curr_idx+1))
width=max(width,curr_idx-top_idx+1)
return width
I modified the formula to 2*node and 2*node+1
This works well on leetcode
Besides none of those long long issues that are being pointed to in the comments
class Solution {
private class Pair{
int idx;
TreeNode node;
Pair(int idx, TreeNode node){
this.idx=idx;
this.node=node;
}
}
public int widthOfBinaryTree(TreeNode root) {
Queue q=new LinkedList();
Pair temp;
int width=0, begin, end, size;
q.add(new Pair(0, root));
while(!q.isEmpty()){
size=q.size();
temp=q.poll();
begin=temp.idx;
end=temp.idx;
if(temp.node.left!=null){
q.add(new Pair(2*end, temp.node.left));
}
if(temp.node.right!=null){
q.add(new Pair((2*end)+1, temp.node.right));
}
for(int i=2;iwidth){
width=end-begin+1;
}
}
return width;
}
}
Instead of taking values of the next nodes as (2*i+1) and (2*i+2), we can take (2*i) and (2*i+1), in this case, it is not required to subtract the minimum of nodes on the same level.
in that case if you have a skew tree with only right nodes it will also cause int overflow
In that case also it's required/helpful, logic is same
If anyone face issue of overflow just a bit change where we subtract min index we have to subtract the max index of current level where we store negative value as index for long width which solve the overflow issue. Below is the code of it.
int widthOfBinaryTree(TreeNode* root)
{
if(root==NULL)
return 0;
queueq;
q.push({root,0});
int res=0;
while(q.empty()==false)
{
int start=q.front().second;
int end=q.back().second;
res=max(res,end-start+1);
int size=q.size();
for(int i=0;ileft!=NULL)
q.push({x.first->left,2*index+1});
if(x.first->right!=NULL)
q.push({x.first->right,2*index+2});
}
}
return res;
}
Heyyy after 3 it must be 7 right at 11:01 because 2*3+1=7 but you have written 6 ??
I we have level, we can say that maximum number of nodes in that level is 2^(level number)
So we can simply find number of level, and use above formula
Aapke explanation ko salaam ❤
We can find the leftHeight and rightHeight of root node. Required value = 2^(min(leftHeight, rightHeight))
At 10:24 in the vid, won't it be 7 instead of 6, at the 4th level node ?? Since it will be 2*3 + 1
Its simple to use level size right
Great Question Striver . Thank you so much !
Ye bandaaa kitna awesome hai yrrrrrr 🫀🫀🫀🫀🥲🫂🫂🫂🫂🫂🫂🫂🫂🫂
bro for taking (last index-first index+1) we can use the formula to find maxx width at the level (2**level)
Instead of doing minn stuff, we can simply use 2*i, 2*i+1 instead of 2*i+1, 2*i+2
Python code:
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
q=[(root,0)]
ans=0
while q:
n=len(q)
mn=q[0][1]
for i in range(n):
curr=q[0][1]-mn
node=q[0][0]
q.pop(0)
if i==0:
first=curr
if i==n-1:
last=curr
if node.left:
q.append((node.left,2*curr+1))
if node.right:
q.append((node.right,2*curr+2))
ans=max(ans,last-first+1)
return ans
No need to use long long or unsigned just make min=q.back().front , it will solve
using long long kills the logic of using new indexing for each level
@Ayush Negi hey like but we never go to 2^3000 . i mean we always subtract the minimal from the indexing so at worst case of 3000 nodes we should be having number froms [0......3001] say. if i am wrong do reply. thanks
The index of the first node of each level, also tells the width of that particular level. Isn't it?
dropping a comment just to motivate you 😊😊😊 btw great series
Hey thanks for the series, loving it. One doubt though :
if what you mention is actually the width of the binary tree then couldn't you simply find this out using a formula? 2^n ?
nope
4
/ \
5 7
\ /
8 9
Consider this tree and u will get ur ans..
This formula is valid for complete binary Tree only.....And binary tree can be of any type
@@varunvishwakarma9689 got it, thank you.
if we just use 2*i for left, 2*i + 1 for right, with zero index tree. we can avoid over flow @takeUforward
I think we can use vertical no and at each node and then subtract it
Each level can can have multiple nodes too.. so it kinda fails
if(node->left){
q.push({node->left, idx*2LL+1});
}
if(node->right){
q.push({node->right, idx*2LL+2});
}
do this on Line 31 and 33 instead before pushing it to the stack, that will fix the overflow!!!
Just curious. Can we just identify level in binary tree and get the result as 2^(max(level)) ?
Understood!! ✨
But I have one question. Is solving these questions on leetcode after watching videos is right or wrong?
Same doubt
think for 10-15 min about the approach and then see the video. Here you are learning about the concept of binary tree not practicing the questions. After learning the basic concept you can go to leetcode to solve different problems on tree. I hope it will help you.
No problem, if you understand the approach. Practice similar questions.
I guess the Vertical order traversal will be an easy approach. Also since we incorporate netative integers there , no overflow will occur .
easier but will lead to the extra Space Complexity of using the map also will increase the time complexity
Hello @take U forward
can we just not calculate the depth of the of the tree and then do 2^(depth-1) ?
It is working for all the cases I thought of
Please let me know if I am thinking in the right direction or not .
Works by just writing long long in queue index
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (root == NULL) {
return 0;
}
int ans = 0;
queue q;
q.push({root, 0});
while (!q.empty()) {
int size = q.size();
int first, last;
for (int i = 0; i < size; i++) {
int cur_id = q.front().second;
TreeNode* node = q.front().first;
q.pop();
if (i == 0)
first = cur_id;
if (i == size - 1)
last = cur_id;
if (node->left) {
q.push({node->left, (long long)2 * cur_id + 1});
}
if (node->right) {
q.push({node->right, (long long)2 * cur_id + 2});
}
}
ans = max(ans, last - first + 1);
}
return ans;
}
};
NICE SUPER EXCELLENT MOTIVATED
If u stuck with runtime error please take a long long variable in place of curr_id in leeetcode same question 662.
Thanku bro
Personal note:
Why we are not subtracting 1 at every level from the index instead taking minimum from queue?
coz it mignt happen only right subtree exists at a level
🙂 couldn't solve by myself. this question follows very nice apoorach
can we use Math.min(lefthheight,rightheight)*2
Doubt:
In GFG, maximum width is defined as maximum nodes present in a particular level.
In Leetcode: maximum width is the distance between 2 corner nodes in a level(including nulls).
Can you confirm that GFG article is false or not?
Not read that, try to follow leetcode.
It can be simplied
Great explanation 👍👍👍
@20:53 I was also thinking 1 will be minimum index for all
curr_id should be of type ` long long`.
Couldn't it also be done in the following way :
I traverse to the left most leaf and store the level as lev1.
Then, I traverse to the right most leaf and store the level as lev2.
I get the minLevel = min(lev1, lev2)
Max width = 2^(minLevel).
Levels start from 0 index.
no it gives you wrong answer because width is max possible nodes between the extreme two node of the tree on the same level
why cant we use the concept of "vertical indexing" which we use on top view of binary tree.
by using this, we can take the first and last element and find the answer
can anyone answer my question?
your implementation ♥♥
Width is calculated between any two nodes as explained initially we ignored the node in second tree in the beginning of the video
How will skew tree with single line nodes can even be a possible test case ?
It wont be a test case, skew tree will yield 0 I guess. Bcs there can never be another node in the same lvl to compare with.
From code we can definitely say value of first is going to be zero. So, we only need to store value of last.
Hence, ans = max(ans, last + 1)
In face without even storing we can solve this.
Follow below code.
/**
* 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 widthOfBinaryTree(TreeNode* root) {
if (root == NULL) {
return 0;
}
int ans = 0;
queue q;
q.push({root, 0});
while (!q.empty()) {
int size = q.size();
int mini = q.front().second;
for (int i = 1; i ans) {
ans = cur_id + 1;
}
}
if (node->left != NULL) {
q.push({node->left, 2 * cur_id});
}
if (node->right != NULL) {
q.push({node->right, 2 * cur_id + 1});
}
}
}
return ans;
}
};
Can someone explain why we did i-curmin, and not just take i ??
if we push (root,1) intially and find cur_idx as cur_idx=q.front().second-1
then their will be no need of making mmin integer
At 10:43 it should be 7 instead of 6 as 2*3 + 1 = 7.
Yeah slight typo.. hope you understand what i was trying to convey.
P.S: human here
@@takeUforward Yeah😅..Thank you so much for your reply and this tree series! Aise hi dp ki bhi leke aana 🙏🙏
This might look easy but very tricky question Thanks #Striverbhaiya for the beautiful explanation :)
doubt
how width is 2 at 17:21.
as only 1 is between 3 and 7, so the answer should be 1 !!
Am talking about indexing..
Can you please clarify my doubt.
imagine there are 3 levels in a tree. first and second levels are completely filled (1 root, 2 (root's left child), 3(roots right child)
but the third level has starting node( 4, (2's left child) ) and (5, (3's left child)).
what should be the solution to the above case, your program is giving 3 as the answer. but should the answer be 2 or 4 or 3 ?
Ans will be 3 as there is only one node(2's right child) to be counted in width.
This code is giving wrong answer at 101/114 test case. Can anybody pointout possible mistakes in it?
int widthOfBinaryTree(TreeNode* root) {
long long int ans = 1, c = 1;
queueq, q2;
q.push(root);
while(q.size())
{
int k = q.size();
vectorv;
for(int i = 0; ileft)
{
q.push(a->left);
v.push_back(a->left->val);
}
else v.push_back(-101);
if(a->right)
{
q.push(a->right);
v.push_back(a->right->val);
}
else v.push_back(-101);
}
if(!q.size()) break;
c *= 2;
long long i = 0, j = v.size()-1;
while(i=i && v[j] == -101) {j--; c--;}
ans = max(ans, c);
}
return ans;
}
For 0 based indexing, Instead of doing (cur_id+1 and cur_id+2) we can do (cur_id and cur_id+1) also.
No we cant level 0 and 1 will work but in level 2 two nodes will have same value
Cant we solve it using 2^level
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root)
return 0;
int ans=0;
queueq;
q.push({root,0});
while(!q.empty()){
int size=q.size();
int min=q.front().second;
int first,last;
for(int i=0; ileft)
q.push({node->left,cur_id*2+1});
if(node->right)
q.push({node->right,cur_id*2+2});
}
ans=max(ans,last-first+1);
}
return ans;
}
};
I wrote ur cpp code but it says wrong ans:)
use long long integer for further overflow
why cant we just find height and do 2^(height-1) as the maxm possible width??
Awesome explanation bro👏
In GFG why this is Giving TLE?
Nice one but I guess it could be made even more simpler if you would have used the concept of vertical level as then you will be just subracting the vertical level of the last node and the first node of a particular horizontal level.
Wow, I haven't thought for this one.
Tried but not working, as 2 overlapping nodes on a particular horizontal level are having same column index.
Won't work, as I have thought of the same approach but see leetcode example 2 you will understand why it will not work
Understood!❤
wonderful explanation !
WE LOVE YOUR CONTENT AND WE LOVE YOU.....🖤
UNDERSTOOD;
I was struggling with overflow error.
bahut bhadiya teaching skill
Striver how did you solved the overflow issue?
C++ Leetcode accepted Solution :
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(!root)
return 0;
int ans=0;
queue q;
q.push({root, 0});
while(!q.empty()){
int size = q.size();
int mmin = q.front().second; // to take the id starting from zero
int first, last;
for(int i=0; ileft)
q.push({node->left, cur_id*2+1});
if(node->right)
q.push({node->right, cur_id*2+2});
}
ans = max(ans, last-first+1);
}
return ans;
}
};
Can't we just use pow(2,n) where n is the max depth of the tree?
no, this doesn't work for all test cases , like 1:58, 2nd example
Great Explanation. Tree series is so awesome
sir I am little bit confuse in the overflow part......like if we have 10^5 nodes int any tree then how it will be the part of stack over flow
when calculating the index we are multiplying the index by two, so just imagine 2 raise to the power some big number exceed the range of the int
@@namanchandra5270 cant we just simply use long long then?
The above code gives runtime error in leetcode because of overflow
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
queue q;
queue secq;
unordered_map umap;
q.push(root);
long long max_width = 1;
umap[root] = 0;
while(!q.empty())
{
TreeNode *curr = q.front();
q.pop();
if(curr->left!=NULL)
{
secq.push(curr->left);
umap[curr->left] = 2 * umap[curr]+1;
}
if(curr->right!=NULL)
{
secq.push(curr->right);
umap[curr->right] = 2 * umap[curr] + 2;
}
if(q.size() == 0)
{
if(secq.size() > 0)
{
TreeNode *first = secq.front();
TreeNode *last = secq.back();
long long f = umap[first];
long long l = umap[last];
long long width = l-f+1;
umap[first] = umap[first]-f;
umap[last] = umap[last]-f;
max_width = max(max_width, width);
}
queue temp = q;
q = secq;
secq = temp;
}
}
return max_width;
}
};
Can anyone review and tell me what's wrong with the code last few testcases on LC are failing
/**
* 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 widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
int ans=0;
queue pendingNodes;//int refers to the index number of the node...in a level the nodes always have index number ranging from (1...size of level)
//any level starts from 1 or 2 and the index of the first node present in that level.
//in practice the nodes which exist will have range from like 2000....something
pendingNodes.push({root,0});
while(!pendingNodes.empty()){
int size=pendingNodes.size();
int minimum=pendingNodes.front().second;
int first,last;
for(int i=0;ileft) pendingNodes.push({node->left,(long long)2*cur+1});//when 2*cur+1 is calculated then the answer is an integer by default as 2,cur,1 aa are integers....but the result circumpassess the int_max limit...so it has to be manually typecasted to long long
if(node->right) pendingNodes.push({node->right,(long long)2*cur+2});
}
//one level processed
ans=max(ans,last-first+1);
}
return ans;
}
};
Cant we say the max width of a binary tree is the max depth of that tree multiplied by 2?
It might be possible that the max depth might not have the maxwidth at all.
In a case where at the max depth/lowest level might have only one node or even if it had 2 nodes the number of nodes in between those two nodes might be lesser than some thing we got at a level above the max depth.
Thus max depth * 2 would become wrong in such cases.
Awesome Explanation. Understood.
Huge respect...❤👏
Very well explained thank you striver
I am not able to understand the problem statement.