# Populating Next Right Pointers in Each Node

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

非递归的方法就是遍历Binary Tree，由于条件限制不能用额外空间extra space，因此level order BFS 所需的queue就不能用了。好在这一题中每层之间最终都会通过指针连接起来，也就让一行之内的遍历成为可能。

在上一层的节点连接起来之后就可以遍历该层，并且连接下一层的子节点。连接子节点分为两种情形：

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

层内移动指针：

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

转到下一层：

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

### Recursion

递归的inexplicit的调用栈不在题目条件的限制内，因此也可以用递归。

递归函数的逻辑其实挺简单，就是把节点1连接到节点2

```
node1.next = node2
```

## Solution

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

```java
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        TreeLinkNode levelStart = root;
        // Move across level
        while (levelStart != null) {
            TreeLinkNode curr = levelStart;
            // 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%)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/trees/populating-next-right-pointers-in-each-node.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.