[Java] Leetcode 117. Populating Next Right Pointers in Each Node II [Binary Tree #4]

[@traviszito6408]

Thanks for this, great solution. Other videos on here were 17 minutes long for some reason. It's nice to get an explanation that is straight forward and clean looking

[@ChanChan-pg4wu]

good explanation, the best found on this problem! Thanks, Eric!

[@linjiafu8546]

how you just got 5k subscription? the most clear explanation I've ever seen!

[@fireflyeeeee2980]

How can dummy.next point to next level? We are changing temp.next right? Could you explain?

[@EricProgramming]

How can dummy.next point to next level? Ans: Remember that head is always pointing to the parent level and the dummy and temp are always pointing to the children level. Once we connect the children level together using dummy and temp pointers, the next level that we want to traverse is the children's children, right? So we need to move our parent point one level down. That's why dummy.next is to give us the new parent node. Got it?

[@fireflyeeeee2980]

@@EricProgramming oh it makes sense now. Couldn't figure out for god's sake, lol. Thank you!

[@praveen3123]

great solution.. since you just created dummy node, how it points to the first element of next level.. i.e how dummy.next is pointing to the left of the root or start of the next level... is it because of temp node?

[@revanthkovuri8660]

@preveen Yes, the temp has the reference of dummy, where dummy.next points to the first Node of that level

[@MeetManga]

If this problem can use extra space then we can write like that: FYI public Node connect(Node root) { Node head = root; if(root == null){ return null; } Queue queue = new LinkedList(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++){ Node node = queue.poll(); if(i < size - 1){ node.next = queue.peek(); } if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } } } return root; }

[@challengeyourmind3937]

Two while loops not necessary.

[@EricProgramming]

But it doesn't hurt the complexity though, what better solution do you have in mind?

[@PrashantKumar-mp5zu]

@@EricProgramming For starting from next level shouldnt it be head=dummy.left

[@EricProgramming]

@@PrashantKumar-mp5zu Nah, dummy node is just a dummy node, it is there to help us connect each level node's next pointer, so dummy.left and dummy.right is always null. So the correct answer here should be head = dummy.next.