Populating Next Right Pointers in Each Node II

The queue solution is easy to derive. The constant-space solution comes from reusing the next pointers you are building as the queue for the next level.

The contract and the key constraint

Each node has the usual binary-tree pointers plus a next pointer:

• left and right describe the tree structure.
• next must point to the node immediately to the right on the same level.
• The rightmost node on every level must have next = None.

The tree can be empty, sparse, or irregular. A node may have only a left child, only a right child, or no children. Node values do not affect the algorithm; only structure and pointer state matter.

The interview constraint is the important part: use constant auxiliary space. The returned root is allowed to be mutated, so the existing next fields are available as output state.

That rules out a queue if we want the follow-up solution. But the queue gives us the correct baseline and exposes the optimization.

Why the queue solution is the right baseline

A level-order traversal processes nodes from left to right, one level at a time. For each level:

1. Remove nodes from the queue in order.
2. Connect each node to the next node removed from that same level.
3. Add the node's non-null children to the queue.
4. Leave the final node's next as None.

The queue provides the key invariant:

While processing a level, the queue exposes that level in left-to-right order. Therefore, the next node in the queue is the correct right neighbor.

A Python baseline looks like this:

from collections import deque

def connect_with_queue(root):
    if root is None:
        return None

    queue = deque([root])

    while queue:
        level_size = len(queue)
        previous = None

        for _ in range(level_size):
            current = queue.popleft()

            if previous is not None:
                previous.next = current
            previous = current

            if current.left is not None:
                queue.append(current.left)
            if current.right is not None:
                queue.append(current.right)

        # Explicitly terminate this level.
        previous.next = None

    return root

This runs in O(n) time because every node is processed once. Its auxiliary space is O(w), where w is the maximum width of the tree. In the worst case, w is proportional to n.

The queue stores an entire frontier of nodes. The optimization is to ask whether the tree already contains another representation of that frontier.

It does: the next pointers.

Turn each level into a linked list

After a level has been connected, its nodes form a linked list from left to right:

level_head -> node -> node -> node -> None

So instead of removing current-level nodes from a queue, we can walk across them using current.next.

While scanning that current-level chain, inspect each node's children:

1. Append the left child if it exists.
2. Append the right child if it exists.
3. Continue to the next node through current.next.

Those children are encountered in exactly the order required for the next level.

A temporary dummy node makes the append operation uniform:

dummy -> first child -> second child -> third child
          ^
       next level head

The dummy node is not part of the tree. It is just a stable anchor before the first real child. Its next field gives us the head of the newly built level without special-casing the first child.

The algorithm maintains two separate chains:

• Read: follow next pointers across the current level.
• Write: create next pointers across the children that form the next level.

That separation is the entire trick. We never need a queue because the current frontier is already a linked list, and we build the next frontier while walking it.

The invariant that makes the rewiring safe

Before every outer-loop iteration, maintain this invariant:

level_head is the leftmost node of the current level, and following next from it visits every node on that level exactly once, from left to right.

During the scan of that level, maintain a second invariant:

The chain beginning at dummy.next contains exactly the non-null children encountered so far, in their required left-to-right order. tail points to the last node in that chain.

Why does appending children in this order produce the correct next level?

• Every child of a current-level node belongs to the next depth.
• The current-level nodes are visited from left to right.
• For each parent, the left child appears before the right child.

Therefore, the sequence

current.left, current.right, next current.left, next current.right, ...

with missing children skipped is exactly the next level from left to right.

At the end of the scan, dummy.next is the next level's head. The algorithm advances level_head to that node and repeats.

The final node in the constructed chain must point to None. A fresh dummy node starts each level with an empty chain, and explicitly setting tail.next = None makes the termination deliberate rather than accidental.

Correctness condition: read the current level through established next links, append every non-null child once in encounter order, terminate the new chain, then advance to its head.

Dry run on a sparse tree

Consider this tree:

        1
       / \
      2   3
     / \   \
    4   5   7

The important connection is on the bottom level. Node 5 must point to node 7, even though they have different parents.

First pass

Initially:

level_head = 1

The current level contains only node 1.

Start with:

dummy -> None
tail = dummy

Scan node 1:

1. Append 1.left, which is 2.
2. Append 1.right, which is 3.

The constructed chain is now:

dummy -> 2 -> 3 -> None

Advance:

level_head = dummy.next
level_head = 2

The first level has been established:

2 -> 3 -> None

Second pass

Now scan the current level through its next pointers:

2 -> 3 -> None

Start a fresh chain:

dummy -> None
tail = dummy

Process node 2:

1. Append 2.left, which is 4.
2. Append 2.right, which is 5.

The next-level chain is:

dummy -> 4 -> 5

Move across the current level:

current = current.next
current = 3

Process node 3:

• It has no left child.
• Append its right child, 7.

The chain becomes:

dummy -> 4 -> 5 -> 7 -> None

So the required cross-parent connection appears naturally:

4 -> 5 -> 7 -> None

The algorithm did not calculate a special relationship between 5 and 7. It simply scanned parents left to right and appended their existing children in order.

Compact edge cases

• Empty tree: level_head is None; return None.
• Single node: the root has no children, so no new level is created. Its next remains None.
• One-sided chain: each level contains one node, so every next pointer remains None.
• Gaps on a level: missing children are skipped. The next non-null child becomes the neighbor, even when it belongs to a later parent.

This is where solutions based on fixed child positions break. A node's right neighbor is not necessarily its parent's right child, its sibling, or any node with a matching array index.

Populating Next Right Pointers in Each Node II in Python

Assume the platform provides a Node class with val, left, right, and next fields.

from typing import Optional

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

        while level_head is not None:
            # Temporary anchor for the next level.
            dummy = Node(0)
            tail = dummy

            # Walk the current level through its established next links.
            current = level_head

            while current is not None:
                if current.left is not None:
                    tail.next = current.left
                    tail = tail.next

                if current.right is not None:
                    tail.next = current.right
                    tail = tail.next

                current = current.next

            # Make the end of the new level explicit.
            tail.next = None

            # Begin the next outer-loop pass at the new level's head.
            level_head = dummy.next

        return root

The state variables each serve a specific obligation:

• level_head identifies the first node of the level being scanned.
• current walks that level through next.
• dummy gives the next level a stable starting point.
• tail marks where the next non-null child should be attached.

The dummy node is temporary and constant-sized. It does not grow with the tree. The algorithm keeps only a fixed number of references regardless of the tree's width.

The method returns the original root after mutating its next pointers. That matches the output contract: the tree structure remains intact, while each level gains its horizontal links.

Pointer hygiene

The most common implementation errors are small but destructive:

1. Assuming every parent has two children.
   Check left and right independently.

2. Connecting a child to its parent's right child.
   The correct neighbor may belong to a different parent several positions away.

3. Walking the next level while still building it.
   During the inner loop, advance with current = current.next. The newly appended children belong to the next level and should not become part of the current scan.

4. Forgetting the final terminator.
   Set tail.next = None so the new level ends cleanly.

5. Using a queue despite the follow-up requirement.
   The queue solution is correct, but it does not satisfy constant auxiliary space.

6. Confusing child pointers with next pointers.
   left and right move down the tree. next moves horizontally across one depth.

If you want to debug the implementation, print each completed level by following next from level_head. That makes the hidden state visible. Pointer problems become much easier when you stop imagining the links and inspect the chain they actually formed.

Complexity and the transferable pattern

The algorithm visits each node once while scanning its level. Each node's children are checked a constant number of times, so the total time complexity is:

O(n)

The auxiliary space is:

O(1)

Only fixed pointer variables and one temporary sentinel are used. The tree's next fields are output state reused as traversal state; they are not an additional queue or stack.

The reusable pattern is broader than this one problem:

When a problem asks you to connect nodes across levels, and those connections can expose the current frontier in order, use the established frontier as the queue and build the next frontier in one pass.

In an interview, make the reasoning visible:

1. Identify how the current level is represented.
2. Define what the current scan guarantees.
3. Append children in left-to-right encounter order.
4. Terminate the new chain.
5. Advance to its head.
6. Return the original structure after mutation.

The durable insight is simple: the output links become the traversal mechanism. Once you recognize that a completed level is already a linked list, the constant-space solution stops looking like pointer magic. It becomes a controlled state transition: scan one chain, build the next, repeat.