# Populating Next Right Pointers in Each Node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node

## First glance

It would be an easy problem if Binary Tree Level Order Traversal works. Yet, a queue is not allow because of that constant space is required.

## Recursion

connecting left and right child is easy, just `node.left.next = node.right`

Before

```
1
/ \
2 3
/ \ / \
4 5 6 7
```

After

```
1
/ \
2 -> 3
/ \ / \
4-> 5 6->7
```

`5`

and `6`

shoud be connectedã€‚

when connecting `4`

and `5`

, `2`

and `3`

is already connected, that is a good news, we can connect `5`

and `6`

using `2.next`

.

```
node.right.next = node.next.left;
```

### Source code *Read on Github*

```
1 /**
2 * Definition for binary tree with next pointer.
3 * public class TreeLinkNode {
4 * int val;
5 * TreeLinkNode left, right, next;
6 * TreeLinkNode(int x) { val = x; }
7 * }
8 */
9 public class Solution {
10
11
12 public void connect(TreeLinkNode root) {
13 // Note: The Solution object is instantiated only once and is reused by each test case.
14 if(root == null || root.left == null || root.right == null) return;
15
16 root.left.next = root.right;
17
18 if(root.next != null){
19 root.right.next = root.next.left;
20 }
21
22 connect(root.left);
23 connect(root.right);
24
25 }
26 }
```