Maximum Width of Binary Tree - | Leetcode-662 | Flipkart, Amazon | Explanation + Live Code
Вставка
- Опубліковано 7 вер 2024
- This is the 26th Video of our Binary Tree Playlist.
In this video we will try to solve a very good and famous Binary Tree problem "Maximum Width of Binary Tree" (Leetcode - 662).
We will do live coding after explanation and see if we are able to pass all the test cases.
We will solve it using BFS and later I will also post a video on the DFS approach.
Problem Name : Maximum Width of Binary Tree
Company Tags : Flipkart, Amazon, VMWare
My Github Solutions : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
you are the best and greaters , from yester i will be regularly posting about leetcode challenge to maintain consistency and will tag you for reference
Thanks a lot ❤️❤️❤️
every time u prove:
sawal tough ni hota..........samjhane wale me dum hona chahiye
literally thanks a bunch🙌
Thank you so much ❤️
Hello guys, i missed to explain the time and space complexity :
Since we visit each node only once, so the time complexity is O(n) where n = number of nodes in the tree
And since we are using queue whose size can go to approximately n, so space complexity will be O(n) roughly.
Thank you all ❤❤❤
best series in binary trees
Bro you are best youtuber❤❤❤
Thank you so much ❤️❤️❤️
bhaiya aap mahan ho... maan gye...itne sare vdo dekh rha tha intution smjh ni aa rha tha..but apne to fad ke rkh diya question ko...thank you bhaiya😘😘
Java:
class Pair {
TreeNode node;
long index;
Pair(TreeNode _node, long _index) {
this.node = _node;
this.index = _index;
}
}
class Solution {
public int widthOfBinaryTree(TreeNode root) {
Deque q = new ArrayDeque();
q.offer(new Pair(root, 0));
long maxi = 0;
while(!q.isEmpty()) {
long leftChildIndex = q.getFirst().index;
long rightChildIndex = q.getLast().index;
maxi = Math.max(maxi, rightChildIndex - leftChildIndex + 1);
int N = q.size();
while(N-- > 0) {
Pair temp = q.poll();
TreeNode curr = temp.node;
long idx = temp.index;
if(curr.left != null){
q.offer(new Pair(curr.left, 2*idx+1));
}
if(curr.right != null){
q.offer(new Pair(curr.right, 2*idx+2));
}
}
}
return (int) maxi;
}
}
JJ to Abhijeet Singh😊
BTW you didn't share your LinkedIn that day.
Thanks bro much needed
class Solution {
public:
typedef unsigned long long int ll;
map levels;
ll best;
void go(ll ind, int level, TreeNode* root){
if(!root)
return;
if(levels.find(level) == levels.end())
levels[level]=ind;
if(levels.find(level) != levels.end()){
best= max(best, ind-levels[level]+1);
}
go(2*ind+1, level+1, root->left);
go(2*ind+2, level+1, root->right);
}
int widthOfBinaryTree(TreeNode* root) {
levels.clear();
go(0, 0, root);
return best;
}
};
DFS Approach
One of the most simplest and easy explanation
Damn, I wasted soo much time to overcome integer overflow, even long long int resulted in overflow.
then i checked your video, i saw unsigned long long int, then i was like -"wow leetcode using such cheap tricks to increase the difficulty".
Awesome ❤️
Thanks for sharing your idea too .
it wasn't a cheap trick,even unsigned long long cannot hold a value as large as 2^3000,leetcode never expected you to use unsigned long long,it expected people to optimize the indexing technique in a way which won't allow overflow
@@vaibhavpratapsingh9956 can you give example code in c++. Might learn something.
@@elakstein refer to takeyouforward's video for the solution and you can also read about the unsigned int's property
i think the reason for this code working is the auto mod property of the unsigned datatype and not the range of Unsigned long long coz even an unsigned long long can never hold a value greater than 2^64-1 and this code will work even if we use simple unsigned int which has a highest possible value of 2^32-1.
You explaination to every question is so good
Yes this code is perfect but for more optimization or for better run-time complexity we can try to indexing each level starting with 0 .
this can be simple done by subtracting the first index to each element index of all elements in a same level . my code implementation for the same is below :-
int widthOfBinaryTree(TreeNode* root) {
int ans = 0;
if(root == nullptr)
return ans;
queue> q;
q.push({root,0});
while(q.size())
{
int start , end ;
int sz = q.size();
int mini = q.front().second; // this is what i have to substract for make 0 based indexing
for(int i =0 ; i left)
q.push({curr->left,2*idx+1});
if(curr->right)
q.push({curr->right,2*idx+2});
if(i==0)
start = idx;
if(i==sz-1)
end = idx;
}
ans = max(ans,end-start+1);
}
return ans;
}
Thank you for sharing ❤️
hey thanks ..you are the best teacher.thanks for the nice explanation.i impressed :) :)
:)
Thank you 🙏😇
Thank You Bro... One request please also explain how to calculate Time and Space Complexity for soln . It would be very helpful
Sure Uday. Sorry i missed it today.
But i have added a comment explaining the TC and SC
Will add in the coming videos for sure.
Thanks a lot for watching ❤️❤️❤️
@@codestorywithMIK No Problem
Man, you are the best
awesome explanation,ur new subscriber 👍 👍
Means a lot. Thank you so much 😇
Simply amazing
Thanks a lot Mohit ❤️
Amazing explanation
if we are writing long long in everywhere instead of defining like you done. Its not passing all test case, but if i write like you have done by defining long long as ll then its apssing all test case. Please tell me why this happening.
Please share your code
One of my friend told me that this came up in one of his interviews and the interviewer asked a follow up question stating that let's say the tree is skewed like linked list and if we keep pushing 2*i+c, then there would be overflow even for unsigned ll. So how would you solve it?
he said something that i did not understand. He said something like jab BFS ho rha hoga, to queue mein push krne se pehle subtract kr lena. No idea what he meant.
Hi there, sorry it’s an old video and I can’t recall. Can you share the exact minute where It’s mentioned.
I will help to clear.
Thanks
Sir can you also explain the DFS approach of this question whose source code you have provided on Github?
Sure, let me soon plan that video too in my free times 🙌
Hello sir could you make a video on leetcode problem no.1530 number of good pair nodes. I was facing difficulty in solving this question. I referred to the solutions on discuss section but did not understand it completely. Kindly take up this question too. Thanks .
Will you upload today's challenge too?
Sorry for the delay.
It’s being uploaded now. Just a little busy this weekend due to festival
Hope you guys will understand ❤️❤️❤️
@@codestorywithMIK nice no issues
Understood
Thank you for watching 😇🙏
Reminder Leetcode 92
❤
Bro I got runtime error:
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
long long res = 0;
queue q;
q.push({root, 0});
while(!q.empty())
{
int size = q.size();
long long start = q.front().second;
long long end = q.back().second;
res = max(res, end-start+1);
for(int i=0; ileft != NULL)
q.push({curr->left, 2*idx+1});
if(curr->right != NULL)
q.push({curr->right, 2*idx+2});
}
}
return res;
}
};
Use unsigned long long
bhai I had a doubt that in normal bfs code we just pop from the queue but in this question why we had to use n--?
Both are BFS only.
However in this Qn, we wanted to process all the nodes in a level at once, so we followed this n- approach.
@@codestorywithMIK got it..thanks
I have seen other solutions where they are starting the leftmost nodes from 0 for each level . They did so because of the case when there is a skew tree of height 3000 . But you did not do anything like that but still it passed all the testcases , how?
datatype unsigned long long int
Yep. I have used unsigned long long
But can you share the code where people have used indexing 0 for each level
@@codestorywithMIK class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(root == NULL)
return 0;
int res = 1;
queue q;
// I am using intialising list
q.push({root, 0}); // also can use make_pair
while(!q.empty())
{
int cnt = q.size();
// start is the index of root node for first level
int start = q.front().second;
int end = q.back().second;
res = max(res,end-start + 1);
for(int i = 0; i left != NULL)
q.push({p.first->left, (long long)2 * idx + 1});
// if right child exist
if(p.first->right != NULL)
q.push({p.first->right, (long long) 2 * idx + 2});
}
}
return res;
}
};
The following solution in JS, is not passing all test cases for me. Can someone please help me with what I'm missing?
function widthOfBinaryTree(root) {
let maxWidth = 0;
const queue = [{ node: root, index: 0 }];
while (queue.length > 0) {
let levelSize = queue.length;
let left = queue[0].index;
let right = queue[queue.length - 1].index;
maxWidth = Math.max(maxWidth, right - left + 1);
while (levelSize--) {
let {node, index} = queue.shift();
if (node.left) {
queue.push({node: node.left, index: 2*index + 1})
}
if (node.right) {
queue.push({node: node.right, index: 2*index + 2})
}
}
}
return maxWidth;
}
nevermind found it.
Glad to know it’s foxed.
Have been travelling this weekend, apologies for delay in replies