LeetCode Maximum Width of a Binary Tree Explained - Java

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[nikostrongioglou]

Initializing the position to 0 produces wrong ids for the leftmost nodes. It works for the case where the bottom level has only two nodes but I cannot understand how the rest of the test cases work. Your solution is valid once you initialize the position it to 1.

[suhasnayak]

Nice video! Just a tip - I think it would be better if you can walk through your logic on a white board, instead of just typing out the code!

[ashishtank]

Organic chemistry in Background board.

[tarsala]

All I hear is: 2 + 2 is 4 minus 1 that's 3. Quick mafs.
And I can't focus anymore :D

[sidddcloud]

to explain the math line. .
at any level. we have saved leftmostpos. . .
then on each node at that level, we are doing (currpos - leftmosepos+1) . this will give the total nodes on that level till that node.
so, when u will eventually get to the right most node till will give u the max width at that level.

[kenzhang]

watched twice finally understand. I suggest to do a search on computeifabsent to understand the full solution. This video is confusing but better than the leetcode discussion.

[mahmoudhamad]

For the testcase that contains multiple nulls and 0s make the position as a Double (both in function argument and hashmap) and when you return it return it as an Int

[ayushd]

Were you studying Organic Chemistry back there on the board before?

[JSDev]

There's actually a more elegant solution that uses a simple arrayList instead of hashmap, since we're doing left call first, the first call of a depth will always be the left most pos in that depth.

[harshitmakhija]

Thanks I find it nice and simple i appreciate your effort

[asrealmadrid]

Awesome, great solution, and intuitive too.

[prashleo]

shouldn't the depth of the root be 1 initially?

[AlbertKamu]

I think they've updated test suit for this one, since this solution won't work anymore.
There is tree with around 1000 levels so it won't be enough any integer for positions.

[yannisb]

Wrong explanation mate. In your code the labels are not 1, 2, 3 etc. They are per depth. So you have 0 for the leftmost node and 2^depth - 1 for the rightmost one, providing the root depth is 0. That's why this works. And you calculate the final max_width for each depth at the rightmost node so you basically subtract its position from the leftmost one and you add 1 because otherwise you would get only the middle nodes.

[JDarkish]

How the fk am i supposed to solve this in a real interview, those rare methods like computeifabsent got me

[jugsma]

Nick, you are complicating your solution.
Here's the simpler version:
def max_width(root, cache, level):
if root == None:
return True

if root.val != None:
if level in cache:
cache[level] = cache[level]+1
else:
cache[level] = 1
max_width(root.left, cache, level+1)
max_width(root.right, cache, level+1)

return cache[len(cache)]

[DEEPAKGOYALnullRA]

class Solution {
public int widthOfBinaryTree(TreeNode root) {
int[] result=new int[1];
maximumWidth(root, 0, 0, result);

return result[0];
}

public void maximumWidth(TreeNode root, int depth, int position, int[] result){

if(root==null) return;
result[0]=Math.max(result[0], position+1);
maximumWidth(root.left, depth+1, position*2, result);
maximumWidth(root.right, depth+1, position*2+1, result);
}
}
can anyone tell me what is the mistake in code

[supremoluminary]

I was not able to understand the strategy. Instead of using hand gestures, I prefer diagrams.

[DEEPAKGOYALnullRA]

awesome concept i got from this video
thanks man

[Subhasish]

To those who have not understand the above explanation hope the below helps

Basically what he is doing is he is maintaining a map where the key is level and the value is the leftmost node position of that level. Now since he is doing a DFS, so he is always calling the left node and then the right node so it is guaranteed that the map would be always initialised with the leftmost value of that level first. Now for each node in recursion if he is seeing that for that level the entry is already there in map then he simply subtracts the value from that level in map(leftMost element of that level) from the position value of the current node and replaces the whole value in max_width if eligible