Leetcode - Maximum Width of Binary Tree (Python)

[@pacomarmolejo3492]

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

[@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.

[@timc3406]

I think the width for your example is still 1 because it's looking at the width level by level, I could be wrong!

[@stephenchen605]

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

[@timc3406]

Great to hear!

[@nirajpatel9196]

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.

[@timc3406]

Awesome to hear! Sure I'll try to think of a way to visualize better

[@austin4855]

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.

[@java-coders5515]

have you got the solution ??, how to handle this kind of situation, I also stuck in this in javascript

[@janmichaelaustria620]

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

[@timc3406]

something like output = [] def dfs(node,level): if len(output) < level+1: output.append([]) if not node: output[level].append(None) if len(output) > level+1: dfs(None,level+1) dfs(None,level+1) return dfs(node.left,level+1) dfs(node.right,level+1) output[level].append(node.val) dfs(root,0) def width(lst): l,r = 0,0 for i in range(len(lst)): l= i if lst[i] is not None: break for j in range(len(lst)-1,-1,-1): r = j if lst[j] is not None: break return r-l+1 return max([width(l) for l in output])

[@midhileshmomidi2434]

This is very easy solution of all

[@sentinel-y8l]

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.

[@aayansrivastava7121]

Hey, can you tell me a little bit more about how to use deltas?

[@scchouhansanjay]

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