Populating Next Right Pointers in Each Node II | Live Coding with Explanation

Populating Next Right Pointers in Each Node II | Live Coding with Explanation | Leetcode - 117

Рет қаралды 21,677

Күн бұрын

Пікірлер: 50

@AlgorithmsMadeEasy 3 жыл бұрын

We hope you all are enjoying our videos!!! Don't forget to leave a comment!!! Please like the video to support us!!! Questions you might like: ✅✅✅[ August Leetcoding Challenge ] : kzbin.info/aero/PLJtzaiEpVo2xu4h0gYQzvOMboclK_pZMe ✅✅✅July Leetcoding challenges: kzbin.info/aero/PLJtzaiEpVo2wrUwkvexbC-vbUqVIy7qC- ✅✅✅June Leetcoding challenges: kzbin.info/aero/PLJtzaiEpVo2xIfpptnCvUtKrUcod2zAKG ✅✅✅May Leetcoding challenges: kzbin.info/aero/PLJtzaiEpVo2wRmUCq96zsUwOVD6p66K9e ✅✅✅Cracking the Coding Interview - Unique String: kzbin.info/aero/PLJtzaiEpVo2xXf4LZb3y_BopOnLC1L4mE Struggling in a question?? Leave in a comment and we will make a video!!!🙂🙂🙂

@subhedarsanchay 3 жыл бұрын

This was indeed a tricky problem. The trick of the problem is that we are traversing two levels at a time: Current level and the children of the current level. Introduction of dummy variable in the code before explaining it made it harder for me to understand it. After spending enough time on it, I see it though. If possible, try and match the code with the explanation. I do see that you go back and explain the dummy variable but by that time, viewer is confused already by seeing it in the code. Also, calling the variable with a meaningful name like `childHead` might have made it easier to understand. Good explanation, regardless.

@AlgorithmsMadeEasy 3 жыл бұрын

Rightly said @sanchay! Should have explained before declaring it. An important point on which I will work in future videos. Thanks for bringing that up. Happy coding!! 🙂

@supreethpadavala5454 Жыл бұрын

Wonderful explanation. Felt the explanation is easier than most of LeetCode discussions and official solution. Not to mention it is highly efficient as well. Great stuff guys. Really great.

@AlgorithmsMadeEasy Жыл бұрын

Thanks !! Glad you like it.

@xinniu3145 2 жыл бұрын

This answer is brilliant !!! Thank you for sharing!!! Let me do some explanation as things are not as straightforward for new learners like me: outer while loop 1: only root is store in queue. The size will be 1, so in the inner while loop we just pop root from the queue and store it in the dummy (dummy = dummy.next). Here node 2 and 3 is added to q. outer while loop 2: Now we go the next round on the q(2,3), here dummy is redefined. It first point to node 2, and then in the next inner loop dummy points to 3 and 3 (dummy.next) is pointed to 2 (dummy). Here 4,5,7 is added to queue. outer while loop 3: dummy.next->4, dummy->4; dummy.next->5, dummy(4)->dummy.next(5); dummy.next->7, dummy(5)->dummy.next(7)

@hasrat17 4 ай бұрын

WOOOOOOOO, Thanks I was not able to come up with this solution

@AlgorithmsMadeEasy 4 ай бұрын

No problem.

@obulpathi2729 Жыл бұрын

Excellent solution...better than the leet code's official solution, it was a little bit complex to understand and implement during the interview. thanks for sharing.

@Rahul-sq6gk 2 жыл бұрын

thanks alott.. the leetcode solution hurt my brain. thanks again

@shreyash1503 3 жыл бұрын

This is brilliant! Superb explaination.

@AlgorithmsMadeEasy 3 жыл бұрын

Thanks !!

@ashisranjandey7541 9 ай бұрын

Best explanation and implementation.

@ThePradeep2010 3 жыл бұрын

I am bit confused on space complexity. As you are creating a new dummy node (from heap space right?) for each outer while loop invocation, you will be creating O(h) dummy nodes (h is height of tree) and hence it is not constant space. Anything I am missing here?

@dheerajvarma574 3 ай бұрын

To make it constant space, create the dummy node and temp node outside of both loops. Now, after inner while loop, make dummy.next = null and temp = dummy

@sakshi-ok8zu 10 ай бұрын

such a neat solution, thanks!

@sommayghosh4617 2 жыл бұрын

Quick and lucid explanation, thank you!

@toshanverma1084 3 жыл бұрын

Very well explained sir. You made the problem really easy. Thankyou sir.

@abhinavkumar5298 Жыл бұрын

Awesome Explanation

@starpomero9983 3 жыл бұрын

Could you please tell me why head = dummy.next; can get value even though you use p next = node.left ? (it seems that you don’t set value for dummy inside roop) if we write TreeLinkNode p = dummy; then dummy could reference the p ? so it means both could take same values?

@vincechen6854 3 жыл бұрын

Thank you so much sir!! You just made my day :)

@AlgorithmsMadeEasy 3 жыл бұрын

Thank you!! 🙂

@paragroy5359 3 жыл бұрын

Nice explanation sir the follow up part is a bit tricky??

@ZeroTrunks 3 жыл бұрын

Since a new node is being made at every level isn't the space complexity O(h) where h is the height of the tree?

@ayushshukla6483 3 жыл бұрын

That's true.

@ManojKumar-vb7wm 2 жыл бұрын

@ratnadeepbhattacharya3237 3 жыл бұрын

You are using the outer while() to traverse the height and inner while() to traverse the level and creating a new node inside the outer while loop. SO in that case you are dynamically creating h nodes where h is the height of BT.....shouldn't the space complexity in that case be O(height) instead of O(1)?

@shamimsarker839 Жыл бұрын

I was thinking the same.. In recursive approach we can achieve O(1) space.

@obito9700 3 жыл бұрын

how its working internally...the code u showed up was easy to understand bt how storing process done of each node?

@MrAaaaaaaa-n8t 2 жыл бұрын

thanks for the video! would you be able to show how do we test the function ourselves in java? like what is the data format of the input we should use.

@Gia713 3 жыл бұрын

Space complexity of BFS is O(N), while you should use O(1) in this problem

@AlgorithmsMadeEasy 3 жыл бұрын

yes, and so I have discussed that approach as well!

@ashwinvarma9349 3 жыл бұрын

please explain dummy node approach, like how the next points to right? please tell in details

@AlgorithmsMadeEasy 3 жыл бұрын

for the dummy node, we also have a temp node which is updated whenever we update its next. this way temp is always at the end and the dummy is at the start. the first node is at the dummy. next, so the head will be updated to it when we need to move to the next level. did it make sense to you?