Leetcode - Maximum Width of Binary Tree (Python)

July 2020 Leetcode Challenge
Leetcode - Maximum Width of Binary Tree

[pacomarmolejo]

Hey Tim! Thanks for the vid. I think this solution is easier to understand and more space efficient
if not root: return
q = deque()
root.val = 1
q.append(root)
mxm = 1

while len(q):
l = len(q)
leftMost = 0
rightMost = 0
for i in range(l):
node = q.popleft()
if i==0:
leftMost = node.val
elif i==l-1:
rightMost = node.val
if node.left:
node.left.val = 2*node.val
q.append(node.left)
if node.right:
node.right.val = 2*node.val + 1
q.append(node.right)
mxm = max(mxm, rightMost - leftMost +1)
return mxm

[nirajpatel]

That helped a lot is it possible if next time when working with trees you can show visual. I find it much easier to understand that I'm sure a lot of others do as well.

[stephenchen]

Very clear explanation! It lets me quickly code out the solution! Thanks Bro!

[AshaYalla]

Nice Explanation but will this work for root - 1, left - null, right - 3. Technically the width should be 2 but leetcode is accepting 1 as solution.

[sentinel-yl]

deque is pronounced deck. this approach would overflow the index integer variable in Java. you can use deltas from the left index to compute the indices of the next level, so your range never exceeds max int.

[austin]

Doesn't this solution result in integer overflow? The problem constraints allow for trees with thousands of layers, at which point repeatedly multiplying index by 2 results in something like 2^3000 as the imaginary index. Maybe I'm missing something, but a very similar approach I tried going with in javascript ended up overflowing.

[janmichaelaustria]

nice vid! would you mind showing your first DFS solution. I tried it for a bit, but then got stuck >.<

[scchouhansanjay]

7:04 think, if you put this disclaimer at the beginning of the video 😂