# 117. Populating Next Right Pointers in Each Node II¶

## Information¶

• Diffculty: Medium

• Created: 2020-01-12 12:08:14

• Last Motified: 2020-01-12 12:08:14

• Tags: Tree, Depth-first Search

## Intuition¶

This problem is almost the same as 116. We could solve this problem by BFS with one additional field level to mark the level of each node.

If the level of current node equals to the level of last visited node, then the next field should be pointed to current node.

## Solution¶

```# Definition for a Node.
# class Node:
#     def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.next = next
from collections import deque

class Solution:
def connect(self, root: 'Node') -> 'Node':
last = None
last_level = -1
queue = deque([[root, 0]])
while queue:
node, level = queue.popleft()
if node is None:
continue
if last_level == level:
last.next = node
last, last_level = node, level
queue.append([node.left, level + 1])
queue.append([node.right, level + 1])
return root
```