# Populating Next Right Pointers in Each Node

## Problem

You are given a **perfect binary tree** where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

```
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
```

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.

Initially, all next pointers are set to `NULL`.

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MNQ2Vkkv00ivore3bDu%2F-MNQ4rpHzi9_Rjd1pNAS%2FScreen%20Shot%202020-11-30%20at%202.38.09%20PM.png?alt=media\&token=9b6e2b76-57fe-4ed7-bcc2-8283ad8a4daa)

### Thought Process

* While traversing a level we will remember the previous node to connect it with the current node

## Solution

```
from collections import deque
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return
        
        queue = deque()
        queue.append(root)
        while queue:
            previousNode = None
            levelSize = len(queue)
            
            for _ in range(levelSize):
                currentNode = queue.popleft()
                if previousNode:
                    previousNode.next = currentNode
                previousNode = currentNode
                
                if currentNode.left:
                    queue.append(currentNode.left)
                if currentNode.right:
                    queue.append(currentNode.right)
        return root

#Time: O(n)
#Space: O(n) b/c of queue
```