# Populating Next Right Pointers in Each Node II

Given a binary tree

```
struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *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`.

**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):

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

        while(root != null){
            TreeLinkNode tempChild = new TreeLinkNode(0);
            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

用一个 dummy node `nextHead`来代表指向下一行的开头节点，并用一个`tail`指针初始化为`nextHead`作为下一行进行连接的指针，当前行则用`curr`表示，当`curr.left`或者`curr.right`不为null，就将tail.next指向它们，并且继续移动`tail = tail.next`

一行遍历结束，也就是`curr = null`，就要重新赋值`nextHead.next`给`curr`，因为`nextHead.next`指向的是下一行的第一个node；

这里要注意`nextHead.next = null;`因为如果不舍为空，那么循环就无法结束。

## Solution

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

```java
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode nextHead = new TreeLinkNode(0); // dummy node for next level
        nextHead.next = root;
        TreeLinkNode tail = null;
        TreeLinkNode curr = null;
        while (nextHead.next != null) {
            tail = nextHead;
            curr = nextHead.next;
            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

```java
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode dummy = new TreeLinkNode(-1);
        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>