Maximum Width of Binary Tree - Leetcode 662 - Python

[@yefetene]

ans = 1
q = deque()
q.append((root,1))
while q:
for i in range(len(q)):
cur,l = q.popleft()
if cur.left:
q.append((cur.left,2*l))
if cur.right:
q.append((cur.right,2*l + 1))
if len(q) > 1:
ans = max(ans, q[-1][1] - q[0][1] + 1)
return ans

[@ADITYA-fk1zy]

Java version:
class Solution {
public int widthOfBinaryTree(TreeNode root) {

Queue q = new LinkedList();

q.offer(new Triplet(root,1,0));
int prevLevel = 0,firstInRow = 1;

int res = 0;
while(!q.isEmpty())
{
Triplet t = q.poll();
TreeNode node = t.node;
int i = t.index;
int level = t.level;
if(level > prevLevel)
{
prevLevel = level;
firstInRow = i;
}
res = Math.max(res,i - firstInRow + 1);
if(node.left != null)
{
q.offer(new Triplet(node.left,2 * i,level + 1));
}
if(node.right != null)
{
q.offer(new Triplet(node.right,2 * i + 1,level + 1));
}
}
return res;
}
}
class Triplet
{
TreeNode node;
int index;
int level;
Triplet(TreeNode node,int index,int level)
{
this.node = node;
this.index = index;
this.level = level;
}
}

[@abhimanyuambastha2595]

Can do this without using a level counter in the queue. Just use the normal iterative bfs where if there is q.len > 0, then run a for loop to pop all. This way we know they are in the same level, and we can easily identify the leftmost and rightmost numbered node.

[@jswlprtk]

Your consistency is inspirational ❤

[@m.kamalali]

i have Same idea but little diffrent implementation
def bfs(node):
q=deque()
q.append([node,0])
width=1
while q :
width=max(width,q[-1][1]-q[0][1]+1)
for _ in range(len(q)):
n,p=q.popleft()
if n.left:
q.append([n.left,2*p+1])
if n.right:
q.append([n.right,2*p+2])
return width
return bfs(root)

[@HarshaVardhan-fu9kv]

Nice dude 🎉

[@def__init]

I like this better bc it’s like our normal BFS format, no prev level calculation

[@catharsis222]

I didn’t look at video (yet), but I’m thinking of just regularly traversing with DFS or BFS, recording depth, and incrementing the value in a hash map with level as key

[@BillyL6]

this was great to see, thanks for the solution

[@steeve1]

My initial thought was to dfs to the deepest node where the max width would be 2^n and tracking leftmost/rightmost where a right child on a left node reduces width by one and vice versa. I wouldn't have come up with assigning the values.
ie. if root.left.left & root.right.right; width =4. If root.right.right were null, but root.right.left, then width would be 3.

[@Nathan00at78Uuiu]

that's what i was thinking too. Keep a count of how deep the tree goes and then 2^n where n is the levels of depth of the tree.

[@brandondavison3099]

This makes more sense to me - level order but use level size to keep track of the level you're on.
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
queue = deque([(root, 1, 0)])
res = 0
while len(queue) != 0:
levelSize = len(queue)
start = end = 0
for i in range(levelSize):
node, val, level = queue.popleft()
if (node.left):
queue.append((node.left, val * 2, level + 1))
if (node.right):
queue.append((node.right, (val * 2) + 1, level + 1))

if i == 0:
start = val
elif i == levelSize - 1:
end = val

res = max(end - start, res)
return res + 1

[@dingus2332]

I dont think you need to track the level , here .Good readable solution btw , thanks !

[@ancai5498]

At the time of trying this issue(12/18/2023: )
The test case failed with overflow (C++), so I made some code changes:
The core idea is for each level, we don't need to know the absolute number, we only need the relative number starting from left most node.
For eg, the leftmost node will always start from 1, when we start a new level, we record the leftmost num, and use (cur.val - leftmost) * 2 + 1 as the next level left value and (cur.val - leftmost) * 2 + 2 as next level right val. Here is the code:
int widthOfBinaryTree(TreeNode* root) {
Node r(root, 1, 0); // root, level, num;
std::queue q;
q.push(r);
int prevLevel = 1;
long leftmost = 0;
long res = 0;
while (!q.empty()) {
Node cur = q.front();
q.pop();
// reaches new level, an alternative would be using for loop, i = 0 as first, i = q.size() - 1 as last.
if (cur.level != prevLevel) {
prevLevel = cur.level;
leftmost = cur.num;
}
res = max(res, cur.num - leftmost + 1);
if (cur.root->left) {
q.push({cur.root->left, cur.level + 1, (cur.num - leftmost) * 2 + 1});
}
if (cur.root->right) {
q.push({cur.root->right, cur.level + 1, (cur.num - leftmost) * 2 + 2});
}
}
return res;
}

[@mohithadiyal6083]

Amazing explanation

[@roywastaken]

this is my favorite routine!

[@SairamDasari2000]

level =1,num =1 happy leetcoding.

[@sitronco]

Love yours videos. I was thinking that another way to fix the bug will be to set prevLevel=-1 in that way we always update the level on the first iteration.

[@palashaa5199]

Good unique solution, but probably unnecessarily complicated given that you've solved plenty of BFS problems before this one and could use a similar level order traversal approach as you've used in the past. You can just use q size in a for loop to tell when nodes in a q are in the same level and find the left and right most node while popping

[@MeanLewisWangChong]

This will not work because q.size() wont account for null nodes, so the width returned will be wrong.

[@palashaa5199]

​​​@@MeanLewisWangChongNull nodes wont matter if you store the indexes of the node in the q. Left nodes are 2n and right nodes are 2n + 1, where n is the index of the parent. You would then simply subtract the index of the left node from the right node and you have your width for that level

[@MeanLewisWangChong]

@@palashaa5199 yup that would work, we maintain a queue of pair of node and index.

[@mrityunjay38]

Is it really intuitive? Not so much. I wouldn't be able to figure out such during an interview for sure.

[@carnaldesire]

Thank you for the clear explanation, the others just go straight into the solution instead of explaining why it works.

[@ayobrrr]

dfs version -
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
dlevelmx={}
dlevelmn={}
def rec(node,x,level):
nonlocal dlevelmx
nonlocal dlevelmn
if node:
if (level not in dlevelmx) or (level in dlevelmx and dlevelmx[level]x):
dlevelmn[level]=x
rec(node.left,x*2,level+1)
rec(node.right,x*2+1,level+1)
rec(root,0,0)
ans=0
for k,v in dlevelmx.items():
x=v
y=dlevelmn[k]
ans=max(ans,x-y)
return ans+1

[@Avarn388]

Great solution but here's what I got:
from collections import deque
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# Initialize the result and a queue for the tree nodes
res = 0
q = deque([(root, 0, 0)])
level_start = {}

# Loop through the queue
while q:
node, depth, pos = q.popleft()

# Store the position of the leftmost node in each level
if depth not in level_start:
level_start[depth] = pos

# Update the result with the maximum width of the current level
res = max(res, pos - level_start[depth] + 1)

# Add the child nodes to the queue
if node.left:
q.append((node.left, depth + 1, pos * 2))
if node.right:
q.append((node.right, depth + 1, pos * 2 + 1))

return res
I used a dictionary to keep track of each node relative to its level. That way it could avoid any bugs prevalent going forward. All in all, it's similar to your approach but I just added that in due to having an error that wasn't the one in your video.

[@jamesisaacson6414]

def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
que = deque([(root, 0)])
result = 1
while que:
new_que = deque([])
for entry in que:
node, index = entry
if not node:
continue
new_que.append((node.left, 2 * index))
new_que.append((node.right, 2 * index + 1))
que = new_que
if que:
temp = que[-1][1] - que[0][1] + 1
result = max(result, temp)
return result//2

[@haoli8983]

Javascript Version.
if didn't let idx to 0. in javascript it will overflow.
var widthOfBinaryTree = function(root) {
if (!root) return 0;
let que = [[root, 1]];
let max = 0;
while(que.length) {
let levelLength = que.length;
const firstIdx = que[0][1]
const lastIdx = que[levelLength - 1][1]
if ((lastIdx - firstIdx + 1) > max) {
max = (lastIdx - firstIdx + 1);
}
for(let i = 0; i < levelLength; i++) {
let [node, idx] = que.shift();
idx -= firstIdx; // !!! without this. overflow will heapean.
if (node.left) {
que.push([node.left, idx * 2]);
}
if (node.right) {
que.push([node.right, idx * 2 + 1]);
}
}
}
return max;
};

[@HistoryHouse45]

cant we do total nodes at max hieght - nodes at last level

[@satorugojo7140]

normalise he positions

[@alexandersmirnov4274]

we can store node index into node.val also we do not need to store level number
int m = 0;
var q = new LinkedList();
root.val = 1;
q.add(root);
while(!q.isEmpty()) {
m = Math.max(m, q.getLast().val - q.getFirst().val + 1);
var level = new LinkedList();
while (!q.isEmpty()) {
var cur = q.pop();
if (cur.left != null) {
cur.left.val = 2 * cur.val;
level.add(cur.left);
}
if (cur.right != null) {
cur.right.val = 2 * cur.val + 1;
level.add(cur.right);
}
}
q = level;
}

[@catharsis222]

I didn’t look at video (yet), but I’m thinking of just regularly traversing with DFS or BFS, recording depth, and incrementing the value in a hash map with level as key