# LeetCode 117: Populating Next Right Pointers in Each Node II

## Problem Restatement

We are given the `root` of a binary tree.

Each node has four fields:

```python
val
left
right
next
```

We must populate every `next` pointer so that it points to the next node on the same level. If there is no node to the right, the `next` pointer should be `None`.

Unlike LeetCode 116, the tree is not necessarily perfect. Some nodes may have only one child or no children.

The official problem also asks us to use constant extra space, excluding recursive stack space. ([leetcode.com](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/?utm_source=chatgpt.com))

For this tree:

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

After connecting:

```text
        1 -> None
      /   \
     2  -> 3 -> None
    / \     \
   4 ->5 -> 7 -> None
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root of a binary tree |
| Output | The same root node after modifying `next` pointers |
| Tree type | General binary tree |
| Next pointer | Points to the next node on the same level |
| Rightmost node | Points to `None` |
| Empty tree | Return `None` |

LeetCode gives this node class:

```python
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
```

The function shape is:

```python
class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        ...
```

## Examples

Consider:

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

At level `0`:

```text
1 -> None
```

At level `1`:

```text
2 -> 3 -> None
```

At level `2`:

```text
4 -> 5 -> 7 -> None
```

Notice that node `5` connects to node `7` even though they do not share the same parent.

For an empty tree:

```python
root = None
```

the answer is:

```python
None
```

## First Thought: Use Breadth-First Search

A direct solution is BFS.

For each level:

1. Store nodes in a queue.
2. Connect adjacent nodes in the queue.

That works correctly.

But the follow-up asks for constant extra space.

So instead of a queue, we should use the already-built `next` pointers to move horizontally across levels.

## Key Insight

While processing one level, we can build the `next` pointers for the next level.

We maintain three pointers:

| Pointer | Meaning |
|---|---|
| `cur` | Current node on the current level |
| `head` | First node of the next level |
| `tail` | Last connected node on the next level |

As we scan the current level using `cur.next`:

1. If `cur.left` exists, append it to the next-level chain.
2. If `cur.right` exists, append it to the next-level chain.

This creates the next level from left to right.

Then we move down:

```python
cur = head
```

and repeat.

## Algorithm

Initialize:

```python
cur = root
```

While `cur` is not `None`:

1. Create:
   1. `head = None`
   2. `tail = None`
2. Walk across the current level using `cur.next`.
3. For each child:
   1. If this is the first child, set `head`.
   2. Otherwise, connect `tail.next`.
   3. Move `tail`.
4. After finishing the level:
   1. Move to the next level with `cur = head`.

Return `root`.

## Correctness

At the start of each outer loop iteration, `cur` points to the first node of the current level, and all `next` pointers on that level are already correct.

The inner loop traverses the entire current level using `cur.next`. For every node, the algorithm processes its children from left to right.

When a child is found:

- If it is the first child discovered on the next level, it becomes `head`.
- Otherwise, it is connected after `tail`.

Thus, children are connected in exact left-to-right order across the next level.

After processing all nodes on the current level, the next level has a complete linked structure through `next` pointers. The algorithm then moves to `head`, which is the first node of the next level.

By repeating this process level by level, all nodes receive the correct `next` pointers. Nodes at the right edge naturally keep `next = None` because no later node is connected after them.

Therefore, the final tree satisfies the required next-pointer structure.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Every node is visited once |
| Space | `O(1)` | Only a few pointers are used |

Here, `n` is the number of nodes.

The algorithm uses no queue and no auxiliary data structure proportional to tree size.

## Implementation

```python
from typing import Optional

# Definition for a Node.
# class Node:
#     def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.next = next

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        cur = root

        while cur is not None:
            head = None
            tail = None

            while cur is not None:
                for child in [cur.left, cur.right]:
                    if child is None:
                        continue

                    if head is None:
                        head = child
                        tail = child
                    else:
                        tail.next = child
                        tail = child

                cur = cur.next

            cur = head

        return root
```

## Code Explanation

Start from the root level:

```python
cur = root
```

The outer loop processes one level at a time:

```python
while cur is not None:
```

`head` stores the first node of the next level:

```python
head = None
```

`tail` stores the last connected node:

```python
tail = None
```

Traverse the current level using already-built `next` pointers:

```python
while cur is not None:
```

Process both children:

```python
for child in [cur.left, cur.right]:
```

Skip missing children:

```python
if child is None:
    continue
```

If this is the first child on the next level:

```python
if head is None:
    head = child
    tail = child
```

Otherwise, append the child:

```python
tail.next = child
tail = child
```

Move horizontally across the current level:

```python
cur = cur.next
```

After the current level is finished, move downward:

```python
cur = head
```

Finally:

```python
return root
```

## Testing

```python
from typing import Optional

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        cur = root

        while cur is not None:
            head = None
            tail = None

            while cur is not None:
                for child in [cur.left, cur.right]:
                    if child is None:
                        continue

                    if head is None:
                        head = child
                        tail = child
                    else:
                        tail.next = child
                        tail = child

                cur = cur.next

            cur = head

        return root

def levels_by_next(root):
    ans = []
    leftmost = root

    while leftmost is not None:
        level = []
        cur = leftmost
        next_leftmost = None

        while cur is not None:
            level.append(cur.val)

            if next_leftmost is None:
                if cur.left is not None:
                    next_leftmost = cur.left
                elif cur.right is not None:
                    next_leftmost = cur.right

            cur = cur.next

        ans.append(level)
        leftmost = next_leftmost

    return ans

def run_tests():
    s = Solution()

    root1 = Node(
        1,
        Node(2, Node(4), Node(5)),
        Node(3, None, Node(7)),
    )

    s.connect(root1)

    assert levels_by_next(root1) == [
        [1],
        [2, 3],
        [4, 5, 7],
    ]

    root2 = Node(1)

    s.connect(root2)

    assert levels_by_next(root2) == [[1]]

    root3 = None

    assert s.connect(root3) is None

    root4 = Node(
        1,
        Node(2, None, Node(5)),
        Node(3),
    )

    s.connect(root4)

    assert levels_by_next(root4) == [
        [1],
        [2, 3],
        [5],
    ]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Sparse tree example | Confirms cross-parent connections |
| Single node | Minimum non-empty tree |
| Empty tree | Confirms base case |
| Missing left child | Confirms general binary tree handling |