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
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.
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. 😭 😭
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
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
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.
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.
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.
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.
@NeetCode i am watching and coding this problem right now. It is saying its wrong. The answer got out dated. Please check and modify it class Solution: def connect(self, root: 'Node') -> 'Node': if not root: return None queue = deque([root])
while queue: size = len(queue) prev = None for _ in range(size): node = queue.popleft() if prev: prev.next = node prev = node
if node.left: queue.append(node.left) if node.right: queue.append(node.right)
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!
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
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/
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
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
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/
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
Thanks!
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
Yeah but the follow up says to do it in O(1) excluding the recursion stack space
Yeah, I did it the BFS way as well. Couldn't really think of a O(1) space solution.
Actually it isn't confusing at all. We are just connecting left child and right child
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.
Can you make a video on populating Next Right Pointers in Each Node II - Leetcode 117?
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. 😭 😭
Wait they rejected you because of this?:(
@@memeproductions4182 yup man :(
They told like you need to work on optimization
@@shourya436 i'm sorry dude
This is why programming interviews are a complete joke. You know the trick or you don't.
@@halahmilksheikh absolutely.
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
This is by far the most intuitive solution thanks Neetcode
Great video, loved the solution. Very easy to visualize!
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
In the currently given example in leetcode, when the cur points to node with val=3, curr.left.next=curr.right this becomes null.
How is it related to binary search? In neetcode practice list, it is under the binary search section. @NeetCode
yeah i have the same question here
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
O(N) recursion stack space 🙂
Not an issue apparently, check leetcode’s follow-up
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.
Wow !!!! I am awed at how you have solved this problem !!! 🙇♂
Most intuitive solution.
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.
Very well explained!
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!
very clear explantation, thank you!
Amazing dude, seems like I am ready for Google ;)
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.
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)
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.
it gets easier but you have to do it everyday
Best video yet
05:20 Optimized Solution
"447. Number of Boomerangs" please solve this problem next at leetcode
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.
Damn, really an awesome solution
thanks!
How to solve the followed up, 117?
Explanation is awesome but your solution only works if the input is a perfect tree, which is not the case of this LC quesiton.
4:35 - 6:10
hey are u providing any dsa courses or else are u teaching all this codes at any specific channel
So clear!
Do you use python while working in Google ??
@NeetCode i am watching and coding this problem right now. It is saying its wrong. The answer got out dated. Please check and modify it
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return None
queue = deque([root])
while queue:
size = len(queue)
prev = None
for _ in range(size):
node = queue.popleft()
if prev:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
prev.next = None
return root
This answer works!!
You're a beast man!
Can you add the java solution in the description of your video please.
It's there in his site
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!
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?
you are given aperfect binary tree means curr.next.left must exist
You're probably doing LC 117 instead of 116.
@@tsunghan_yu thank you, I had the same problem
mannnnn this is great!
117. Populating Next Right Pointers in Each Node II
Need
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.
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
By optimal he's saying it does not using extra memory while ur solutions using o(n) memory in system stack because of recursion
@@lordsixth5944 Yep, i was just trying to make the recursive equivalent for what its worth
FYI, *node* has been replaced with *root*
Can you make on this also... plz.. 117. Populating Next Right Pointers in Each Node II
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/
That O(1) solution is brilliant. I coded up the "regular" BFS solution in 2 minutes, but this - this is so much better.
bro...what? lol. I just did a regular BFS. Awesome solution btw.
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
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
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
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/
chef kiss
It doesn't work any more.
Quite a deceptive problem.
cur in while is not neccesary, I have verified it.
man, is it just me, or anyone else getting runtime error?
notification squad
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
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.
@@horcruxoneI see. Thanks!
c++ code anyone?