Populating Next Right Pointers in Each Node

The algorithm uses BFS with a trace of the level.

While the queue is not empty:

If the current level is different from the precedent that means that the precedent node was the rightest of its level and should point to None.

Otherwise that means that the precedent node is the left neighbour of the current one and should point to it

If the current node is not None set the prec_node to this node and add its children to the queue with the correct level

from collections import deque

def connect(root: 'Optional[Node]') -> 'Optional[Node]':
    q, level = deque(), 0
    q.append((root, level))

    while q:
        node, i = q.popleft()

        # if we start a new level that means that prec_node was the rightest of its level and should point to None
        if i != level:
            prec_node.next, level = None, i
        # otherwise the left neighbour (pop just before this one) point to current node (not for 1st node)
        elif i > 0:
            prec_node.next = node

        # set prec_node to node and add its children in the queue with their corresponding level
        if node:
            prec_node = node
            q.extend(((node.left, i+1), (node.right, i+1)))

    return(root)