Populating Next Right Pointers in Each Node - Leetcode 116 - Python

[@omerule0]

Hello, fantastic approach. I solved this problem with maths. The n'th layer has 2 to the power of n-1 nodes. I used breadth firist search and while I was pushing and popping from the queue, I was also counting the steps I took. If the steps were lower than pow(2, power), link it to the next element in queue; if its equal, link it to nullptr and increase power by one and set the counter to zero. Hope this helps somebody.

[@DavidDLee]

My approach was to do a standard layer by layer BFS and just ensure the order of the layer is left to right. I think it is better only because it looks exactly like a standard BFS, without confusing expressions like cur.left.next = cur.right

[@tanishq2766]

Yeah but the follow up says to do it in O(1) excluding the recursion stack space

[@mgnfy-view]

Yeah, I did it the BFS way as well. Couldn't really think of a O(1) space solution.

[@floatingfortress721]

Actually it isn't confusing at all. We are just connecting left child and right child

[@numberonep5404]

Nice solution, i tried to refactor your optimal solution and add comments so it could make sens to me class Solution: def connect(self, root: 'Optional[Node]') -> 'Optional[Node]': n_0, n_1 = root, root.left if root else None # n_0 is our pointer to the current layer # n_1 is our pointer to next layer # We use n_0 to connect all the nodes belonging to next layer, meaning the layer n_1 belongs to. while n_1: # while there is a next layer to connect, we continue n_0.left.next = n_0.right # 1st action we can always do if there is a next layer after n_0 if n_0.next: # 2nd action we might be able to do if we are not all the way to the right n_0.right.next = n_0.next.left n_0 = n_0.next continue # we keep going to the "right" until the layer is all connected n_0, n_1 = n_1, n_1.left # "Recursive call" to handle the next layer # The "Recursive call" can only happen because we used n_0 to connect the layer n_1 belongs to, # And we will use n_1 to connect the layer n_2 belongs to and so on. # There are only two types on connections to build at most, and we can do it from n_0 everytime return root

[@SkyeTian]

More concise? -- class Solution: def connect(self, root): cur, nxt = root, root.left if root else None while cur and nxt: cur.left.next = cur.right if cur.next: cur.right.next = cur.next.left cur = cur.next else: cur = nxt nxt = cur.left return root

[@wrishavbhattacharyya5216]

This is by far the most intuitive solution thanks Neetcode

[@smart7868]

Simple pre-order recursion class Solution: def connect(self, root: 'Optional[Node]') -> 'Optional[Node]': if root and root.left: root.left.next = root.right if root.next: root.right.next = root.next.left self.connect(root.left) self.connect(root.right) return root

[@rickk3300]

O(N) recursion stack space 🙂

[@tanishq2766]

Not an issue apparently, check leetcode’s follow-up

[@ladydimitrescu1155]

Can you make a video on populating Next Right Pointers in Each Node II - Leetcode 117?

[@horcruxone]

the problem has been changed now and they no longer give a "perfect binary tree". As such you will get errors with the above code.

[@sarthakchafle]

In the currently given example in leetcode, when the cur points to node with val=3, curr.left.next=curr.right this becomes null.

[@Vivek_Hatte]

Great video, loved the solution. Very easy to visualize!

[@shourya436]

Ohhhhh man!!!! I had my Google interview today and guess what I proposed the same bfs solution and later he asked for O(1) space solution. Only if you could have uploaded this video earlier, i would have made it. 😭 😭

[@memeproductions4182]

Wait they rejected you because of this?:(

[@shourya436]

@@memeproductions4182 yup man :( They told like you need to work on optimization

[@memeproductions4182]

@@shourya436 i'm sorry dude

[@halahmilksheikh]

This is why programming interviews are a complete joke. You know the trick or you don't.

[@hillarioushollywood4267]

@@halahmilksheikh absolutely.

[@aadil4236]

I did it with the queue data structure initially. It did pass but the code was too much. But you did it so efficiently! Neat code indeed! Thanks!

[@BZ2EZSWE]

You can make it run slightly faster by keeping the while loop as while nxt: because we want to stop when the nxt node pointer is null meaning current is the leftmost leaf node and next is null.

[@mr.unknown4124]

I am a beginner and despite efforts i am not getting good at it. my approach is i try to solve it myself, watch the video understand it and solve it but after sometimes if i approach the problem again it's nearly imposible for me to come up with a solution. Is this normal or am I doing something wrong.

[@baghi_w]

it gets easier but you have to do it everyday

[@vdyb745]

Wow !!!! I am awed at how you have solved this problem !!! 🙇‍♂

[@vikaskumarojha8616]

Most intuitive solution.

[@jhinthefourth8838]

Explanation is awesome but your solution only works if the input is a perfect tree, which is not the case of this LC quesiton.

[@kishores5121]

How is it related to binary search? In neetcode practice list, it is under the binary search section. @NeetCode

[@kyraluu]

yeah i have the same question here

[@040princekumarverma4]

I dont understand the code. Since there are several testcases which are not going to be solved by this code.(in my view) . For example consider testcase: [ 1, null, 2, 3, 4 ]. Since the loop will works only if the root and root.left both are not None .But in the above test case we can clearly see that the (root != None but root.left != None) loop wil not work at all and tree's root is returned without any change to it. If i am wrong please to correct me.(That will help alot) Thanks.

[@seohyeongjeong]

Thanks for going through the problem step by step. I was wondering the difference between writing cur.left.next = cur.right in line 16 instead of nxt.next = cur.right.

[@SkyeTian]

We can't do nxt.left 'cause nxt is always the first cur left node while cur goes on to the next one (i.e., to its right)

[@floatingfortress721]

Wow in ten minutes you covered three approaches: BFS with queue, DFS recursive, and two pointer leveraging techniques from the other two approaches. Awesome job!

[@ankurbhambri9199]

"447. Number of Boomerangs" please solve this problem next at leetcode

[@ankitgoyal8556]

Amazing dude, seems like I am ready for Google ;)

[@selfishmango]

Do you use python while working in Google ??

[@Immaybenotforthenextsecond]

117. Populating Next Right Pointers in Each Node II Need

[@vantrongvo6468]

very clear explantation, thank you!

[@andreytamelo1183]

Thanks!

[@numberonep5404]

The equivalent solution with "actual" recursion of the most optimal solution you presented(i think it is?? Anyone can correct me if you think i am wrong) class Solution: def connect(self, root: 'Optional[Node]') -> 'Optional[Node]': def dfs(node, nxtLayerNode): if nxtLayerNode: node.left.next = node.right while node and node.next: node.right.next = node.next.left node = node.next node.left.next = node.right dfs(nxtLayerNode, nxtLayerNode.left) dfs(root, root.left if root else None) return root

[@lordsixth5944]

By optimal he's saying it does not using extra memory while ur solutions using o(n) memory in system stack because of recursion

[@numberonep5404]

@@lordsixth5944 Yep, i was just trying to make the recursive equivalent for what its worth

[@rafishaik2496]

hey are u providing any dsa courses or else are u teaching all this codes at any specific channel

[@jiahongdai9782]

How to solve the followed up, 117?

[@midasredblade236]

FYI, *node* has been replaced with *root*

[@CST1992]

That O(1) solution is brilliant. I coded up the "regular" BFS solution in 2 minutes, but this - this is so much better.

[@akshayagarwal9311]

Best video yet

[@icedmosha6375]

Damn, really an awesome solution

[@SlateCode]

Can you make on this also... plz.. 117. Populating Next Right Pointers in Each Node II

[@gopeshkhandelwal9823]

I solved it using the above approach. Following is my code- leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/solutions/4376497/o-n-time-complexity-o-1-space-complexity-without-recursion-solution/

[@vaalarivan_p]

4:35 - 6:10

[@FUNTasticFlutter]

this exact same code not working for mw failing fiest test case class Solution: def connect(self, root: 'Node') -> 'Node': cur,nxt = root, root.left if root else None while cur and nxt: if cur.left: cur.left.next = cur.right if cur.next: cur.right.next= cur.next.left cur = cur.next if not cur: cur = nxt nxt= cur.left return root

[@basileatsougan]

The problem has changed now.In the video, it was about a PERFECT BINARY TREE, now in the leetcode problem, the binary tree is not a perfect binary tree

[@ismaelmehdid]

thanks!

[@ihsannuruliman3656]

Hi, could you make a video on 542. 01 Matrix? I'm terrible at graph and all the videos on YT about it kinda asumming people already know about graph.

[@PlamenTheArmwrestler]

Can you add the java solution in the description of your video please.

[@suraj8092]

It's there in his site

[@sabrinahossain8958]

05:20 Optimized Solution

[@yueyue04011]

So clear!

[@gilly4115]

I get an error from line 16. If cur.next.left does not exist on line 18, the cur.left.next is an None type. Am I missing something?

[@rishabhkhurana7203]

you are given aperfect binary tree means curr.next.left must exist

[@tsunghan_yu]

You're probably doing LC 117 instead of 116.

[@vvek_7]

@@tsunghan_yu thank you, I had the same problem

[@butoyighyslain171]

mannnnn this is great!

[@Dhanushh]

chef kiss

[@vgsuresh]

was anyone able to solve `117. Populating Next Right Pointers in Each Node II` with this same approach ? I am kind of stuck with few test cases

[@gopeshkhandelwal9823]

I solved it using the same approach. Following is my code- leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/solutions/4376497/o-n-time-complexity-o-1-space-complexity-without-recursion-solution/

[@bashaarshah2974]

You're a beast man!

[@metarus208]

Quite a deceptive problem.

[@Sheverdin]

It doesn't work any more.

[@starstarhaha]

cur in while is not neccesary, I have verified it.

[@scienceshorts1234]

man, is it just me, or anyone else getting runtime error?

[@ax5344]

I cannot find the python code in OP's website, but with the code I copied from the video, it is showing Null errors in 2024 March. Here is the (not working) code: class Solution: def connect(self, root: 'Node') -> 'Node': cur, nxt = root, root.left if root else None while cur and nxt: cur.left.next = cur.right if cur.next: cur.right.next = cur.next.left cur = cur.next if not cur: cur = nxt nxt = cur.left return root

[@horcruxone]

the problem has been changed now and they no longer give a "perfect binary tree". As such you will get errors with the above code.

[@ax5344]

@@horcruxoneI see. Thanks!

[@scienceshorts1234]

c++ code anyone?

[@FreeStuff4TheWorld]

notification squad