# Populating Next Right Pointers in Each Node

Given a binary tree

``````struct TreeLinkNode {
}
``````

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`.

Note:

• You may only use constant extra space.
• Recursive approach is fine, implicit stack space does not count as extra space for this problem.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Example:

Given the following perfect binary tree,

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

After calling your function, the tree should look like:

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

## Analysis

#### Non-recursion

1. 该节点的左右子节点进行连接
2. 该节点的右子节点和同层邻近下一个节点的左子节点相连接

``````curr = curr.next;
``````

``````levelStart = levelStart.left;
``````

#### Recursion

``````node1.next = node2
``````

## Solution

Use level start TreeLinkNode - O(1) space, O(n) time

``````/**
* Definition for binary tree with next pointer.
*     int val;
*     TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
if (root == null) {
return;
}
// Move across level
while (levelStart != null) {
// Move within level
while (curr != null) {
if (curr.left != null)  curr.left.next = curr.right;
if (curr.right != null && curr.next != null) curr.right.next = curr.next.left;
curr = curr.next;
}
levelStart = levelStart.left;
}
}
}
``````

Use recursion - (3ms 29.60%)

``````public class Solution {
if (root == null) {
return;
}
connectHelper(root.left, root.right);
}
if (node1 == null || node2 == null) {
return;
}
node1.next = node2;
connectHelper(node1.left, node1.right);
connectHelper(node1.right, node2.left);
connectHelper(node2.left, node2.right);
}
}
``````