# 116. Populating Next Right Pointers in Each Node
Question Link is here.
There are two solutions for this problem.
# Solution 1
The first one is quiet obvious, we can use BFS to traverse each level of the tree. And during the traverse of one level, we can point the current node to the next node in line. And after finishing traverse the current level, we can traverse the next level, until no node is left. So here's the code.
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root == None:
return root
cur = [root]
while len(cur) != 0:
temp = cur
cur = []
while len(temp) != 0:
node = temp.pop(0)
node.next = temp[0] if len(temp) != 0 else None
if node.left != None:
cur.append(node.left)
if node.right != None:
cur.append(node.right)
return root
# Solution 2
As for solution 2, we can take advange of the next pointer of each node and the hierarchy of the tree.
We can find that node.left.next = node.right and node.right.next = node.next.left. The difference between solution 2 and solution 1 is that in solution one, as we travel through the current level, we only mark the nodes is the current level, while in solution 2, we mark the next points for the next level. And here's the node.
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root == None:
return root
cur = root
while cur.left is not None:
node = cur
while node is not None:
node.left.next = node.right
node.right.next = node.next.left if node.next is not None else None
node = node.next
cur = cur.left
return root