Populating Next Right Pointers in Each Node II

Problem: Populating Next Right Pointers in Each Node II

We can use two pointers to find head of every level and scan through it until end of the level. Besides, we need a pointer to parent node in previous level and that pointer's next pointer points to the parent of children next to our node in current level.

Code in Python:

class Solution(object):
    def connect(self, root):
        tail = head = TreeLinkNode(0)
        while root:
            tail.next = root.left
            if tail.next:
                tail = tail.next
            tail.next = root.right
            if tail.next:
                tail = tail.next
            root = root.next # next node in previous level
            if not root: # if no next node in previous level, switch to next level
                tail = head
                root = head.next