662. Maximum Width of Binary Tree | LeetCode Daily Challenge | LeetCode POTD

0:00​ - Question Understanding
2:24 - Intuition
11:30 - Code
14:30 - Complexity

#coding #dsa #leetcode #daily #programming #cpp #tutorial

[deepintotech]

class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
int width = 0;
queue<pair<TreeNode*, int>>q;
q.push({root, 0});

while (!q.empty()) {
int n = q.size();
int maxIdx = INT_MIN, minIdx = INT_MAX;
int startIdx = q.front().second;
while (n--) {
TreeNode* node = q.front().first;
int idx = q.front().second - startIdx;
q.pop();
maxIdx = max(maxIdx, idx);
minIdx = min(minIdx, idx);
if (node->left) {
q.push({node->left, (long long)2*idx+1});
}
if (node->right) {
q.push({node->right, (long long)2*idx+2});
}
}
width = max(width, maxIdx-minIdx+1);
}
return width;
}
};