Maximum Width of Binary Tree - | Leetcode-662 | Flipkart, Amazon | Explanation + Live Code

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

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[sidharthdhiman]

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

[oqant]

every time u prove:
sawal tough ni wale me dum hona chahiye
literally thanks a bunch🙌

[codestorywithMIK]

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

[pritimurmu]

Thank You so much.U r a saviour.I was almost annoyed with this question.Offcourse the code is short but my head was filled with Why..why...why are we doing this!!!!..Thank you very very very

[JJ-tpdd]

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

[pragatipatra]

hey thanks ..you are the best teacher.thanks for the nice explanation.i impressed :) :)
:)

[vineetkumarmotwani]

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?

[MohdShahrukh-nenc]

One of the most simplest and easy explanation

[recessionriche]

Will you upload today's challenge too?

[shivamsingh-mimn]

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

[devs]

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.

[elakstein]

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

[ramankr]

Sir can you also explain the DFS approach of this question whose source code you have provided on Github?

[whateverittakes]

awesome explanation, ur new subscriber 👍 👍

[superworker]

class Solution {
public:
typedef unsigned long long int ll;
map<ll, ll> 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

[VivekGupta-inqu]

You explaination to every question is so good

[horccruxxxop]

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

[prajwalshaw]

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 .

[molyoxide]

Bro I got runtime error:

class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
long long res = 0;

queue<pair<TreeNode*, long long>> 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; i<size; i++)
{
TreeNode* curr = q.front().first;
int idx = q.front().second;

q.pop();

if(curr->left != NULL)
q.push({curr->left, 2*idx+1});

if(curr->right != NULL)
q.push({curr->right, 2*idx+2});
}
}

return res;
}
};

[ghanashrim]

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