# Populating Next Right Pointers in Each Node II

Posted: 23 Mar, 2021

Difficulty: Moderate

#### You are given a binary tree of ‘N’ nodes. The nodes are numbered 1 to ‘N’.

#### Your task is to find the ‘next’ node that is immediately right in the level order form for each node in the given tree.

#### Note:

```
1. Node ‘U’ is said to be the next node of ‘V’ if and only if ‘U’ is just next to ‘V’ in tree representation.
2. If there is no next right node, then the next pointer has to be ‘NULL’. Particularly root node and rightmost nodes have ‘next’ node equal to ‘NULL’.
3. Each node of the binary tree has three-pointers, ‘left’, ‘right’, and ‘next’. Here ‘left’ and ‘right’ are the children of a node, and ‘next’ is one extra pointer that we need to update.
```

##### Input Format :

```
The first line contains an integer 'T' which denotes the number of test cases to be run.
The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
For example, the input for the tree is depicted in the below image.
```

```
For example, the input for the tree depicted in the above image would be :
1
2 3
4 -1 5 6
-1 -1 -1 -1 -1 -1
```

#### Explanation :

```
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = null (-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
```

#### Note :

```
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 -1 -1 -1 -1 -1
```

#### Output Format :

```
For each test case, print the tree’s level order traversal after updating the ‘next’ for each node where ‘-1’ denoting the null node.
The output of each test case will be printed in a separate line.
```

##### Note :

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

#### Constraints :

```
1 <= T <= 5
0 <= N <= 3000
1 <= data <= 3000
Where ‘data’ is the value of the node of the binary tree.
Time Limit : 1 sec
```

Approach 1

The idea here is to use **BFS**, which is nothing but the level order traversal. We can maintain all nodes of the same level together by using the **queue** data structure. For a particular node, we start **popping** nodes sequentially and always update the **next** pointer of the just popped node with the current node.

**Steps:**

- If the
**root**is initially**NULL**, then just**return**root. - Create a
**queue**to store all nodes which are going to be explored, and push**root**. - Run a while loop until the queue becomes empty:
- Create a variable named
**previous**to store the previously popped node. - Create a variable named
**n**to store the current queue size. - Run a for loop from
**i**= 0 to**i**= n, i.e., to traverse all nodes of the current level, in each iteration:- Store the front node in the variable named
**current**, and pop the node from the queue. - If this is not the left-most node, then update the previous.
**next**= current. - Push the
**child**of this node into the queue. - Update
**previous**with the**current**.

- Store the front node in the variable named

- Create a variable named
- Finally, return the root.

Approach 2

The idea is similar to Approach 1, but the difference is that we are not going to use a queue here. Let us three-**pointers** at each level to work as a queue. For a particular level, we deal with all its nodes and update regularly the **next**. After the **end** of the current layer, move to the **next level** using our pointers.

**Steps:**

- If the
**root**is initially**NULL**, then just**return**root. - Create a variable
**dummy**consist of null values of left, right, and next. - Create a variable named
**point**, and set it as dummy. - Create another variable
**head**, and initialize it with root. - Run a while loop until the
**head**is not NULL:- Create a variable
**temp**, and initialize it with**head**. - Run a while loop until
**temp**is not NULL:- If the
**left**child is present, then:- Set point.
**next**= temp.left **point**= point.next

- Set point.
- If the
**right**child is present, then:- Update point.
**next**= temp.right **point**= point.next

- Update point.
- Update
**temp**with its next.

- If the
- Now, we have to move to the next level.
- Update
**head**with the next of**dummy**. - Set dummy.
**next**= NULL - Update
**point**to**dummy**.

- Create a variable
- Finally, return the root.

SIMILAR PROBLEMS

# Postorder Traversal

Posted: 22 Jul, 2021

Difficulty: Easy

# Preorder Traversal

Posted: 22 Jul, 2021

Difficulty: Easy

# Get Path using BFS

Posted: 22 Jul, 2021

Difficulty: Easy

# Maximum Sum BST

Posted: 27 Jul, 2021

Difficulty: Hard

# Vertical Sum in BST

Posted: 27 Jul, 2021

Difficulty: Moderate