# Populating Next Right Pointers in Each Node II

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.

Example:

Given the following binary tree,

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

After calling your function, the tree should look like:

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

## Analysis

A very concise and clear level-order traversal (@davidtan1890):

``````public class Solution {
public void connect(TreeLinkNode root) {

while(root != null){
TreeLinkNode currentChild = tempChild;
while(root!=null){
if(root.left != null) {
currentChild.next = root.left;
currentChild = currentChild.next;
}
if(root.right != null) {
currentChild.next = root.right;
currentChild = currentChild.next;
}
root = root.next;
}
root = tempChild.next;
}
}
}
``````

Iterative

## Solution

Iterative - O(n) time, O(1) space

``````public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode nextHead = new TreeLinkNode(0); // dummy node for next level
TreeLinkNode tail = null;
TreeLinkNode curr = null;
while (nextHead.next != null) {
while (curr != null) {
if (curr.left != null) {
tail.next = curr.left;
tail = tail.next;
}
if (curr.right != null) {
tail.next = curr.right;
tail = tail.next;
}
curr = curr.next;
}
}
}
}
``````

Recursive

``````public class Solution {
public void connect(TreeLinkNode root) {
if (root == null)
return;
for (TreeLinkNode curr = root, prev = dummy; curr != null; curr = curr.next) {
if (curr.left != null){
prev.next = curr.left;
prev = prev.next;
}
if (curr.right != null) {
prev.next = curr.right;
prev = prev.next;
}
}
connect(dummy.next);
}
}
``````

## Reference

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37828/O(1)-space-O(n)-complexity-Iterative-Solution

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37828/O(1)-space-O(n)-complexity-Iterative-Solution/35897