LeetCode Maximum Width of a Binary Tree Explained - Java

[@nikostrongioglou9941]

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.

[@treyawey3878]

Initialising the position of the root with 1 is a trick used for heaps.

[@suhasnayak4704]

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!

[@aasimkhan3198]

yeah

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

[@tarsala1995]

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

[@mahmoudhamad6986]

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

[@kenzhang1448]

lol.......ehhhh 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.

[@ashishtank9747]

Organic chemistry in Background board.

[@JSDev776]

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.

[@ayush03d]

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

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

[@pranjalchoubey5929]

This solution worked perfectly for me!

[@harshitmakhija6817]

Thanks I find it nice and simple i appreciate your effort

[@yannisb2178]

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.

[@sidddcloud]

if you take root pos as 1 , you will get the number as he said in the video and it works too. . you can give any no to the root. left most node doesnt have to be at 0 and rightmost as 2 powered depth -1 . left just need to be at parent*2. and right at parent*2+1 . u can start with any number. he said 1 , 2 , 3 in the video bcuz he took root at 1 while explaining. (in code he took 0 , u can take it as any number). positions are not marked as per depth, they are marked relative to the root ( parent to be exact).

[@yannisb2178]

@@sidddcloud If you run the algorithm and start with position 0 you will have something like below 0 --------- depth 0 / \ 0 1 --------- depth 1 / \ / \ 0 1 2 3 --------- depth 2 / \ / \ / \ / \ 0 1 2 3 4 5 6 7 --------- depth 3 So max_width is rightmost-leftmost +1(so for depth 3 it's 7-0+1 = 8). It's essentially the same thing because you have the same difference but I'm saying what he coded which is different and it might confuse some beginners

[@Subhasish8844]

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

[@mananvarma5944]

Hey thanks a lot man! This helped more than the video did.

[@asrealmadrid97]

Awesome, great solution, and intuitive too.

[@prash11leo]

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

[@jugsma6676]

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)]

[@Subhasish8844]

You sure its working?? doesnt look like

[@iamnoob7593]

Good problem.I did this using BFS.

[@viniciusguimaraes117]

How?

[@iamnoob7593]

@@viniciusguimaraes117 check leetcode solution section

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

[@raghuroh1835]

Do not initialize max_width to 0;

[@JDarkish]

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

[@Subhasish8844]

that line is same as if(levelMap.get(level) == null) levelMap.put(level,position);

[@DEEPAKGOYALnullRA]

awesome concept i got from this video thanks man

[@krishna100982]

waiting for 300plus leetcode solns...

[@jiangtianfeng5971]

genius....

[@mridulghanshala700]

i think u should pass 1 to the position variable

[@HarishAmarnath]

yes, i dont know how this works

[@DEEPAKGOYALnullRA]

0.. will only come otherwise it will give wrong answer its better to draw a tree for this code you will get why here 0 comes not 1. if you see in right call he is adding 1 every time this will play a important role in this code so you will get this only after tracing a tree.

[@sidddcloud]

@@DEEPAKGOYALnullRA u can take any number. eg if u take 10. left child will be 20, right at 21. width will still be 2. (21-20+1). now pos 10 sibling will be at 11. its child will be at 22, 23 ( exactly where u want it to be. .) so , on the next level. pos will be 20, 21, 22, 23. . So, it doesnt matter where u begin.

[@sameerpande7567]

Just find the number of levels and raise it to the power of 2 TreeNode traverserLeftNode = Tree.root; TreeNode traverseRightNode = Tree.root; int leftNodeLevel = 0; int rightNodeLevel = 0; while (traverserLeftNode.getLeftChild() != null) { leftNodeLevel += 1; traverserLeftNode = traverserLeftNode.getLeftChild(); } while (traverseRightNode.getRightChild() != null) { rightNodeLevel += 1; traverseRightNode = traverseRightNode.getRightChild(); } int x = Math.max(leftNodeLevel, rightNodeLevel); System.out.println(Math.pow(2, x));

[@sameer9368]

Position value should be 1....I think

[@sameer9368]

In case,everytime 0 multiply by 2 , it will give the leftmost position value as 0 only

[@DEEPAKGOYALnullRA]

it is totally correct 0.. will only come otherwise it will give wrong answer its better to draw a tree for this code you will get why here 0 comes not 1. if you see in right call he is adding 1 every time this will play a important role in this code so you will get this only after tracing a tree.

[@sidddcloud]

@@DEEPAKGOYALnullRA u can take root value anything.

[@atrichaturvedi6322]

This should be a hard level problem

[@enigma2886]

ikr :(

[@ustapc]

please use the whiteboard