Populating Next Right Pointers in O(1) Space

"Populating Next Right Pointers" shows up again and again in Meta, Microsoft, Amazon phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Tree BFS pattern quickly and code it cleanly. Part 7 of 11 in the Tree BFS arc.

The Problem

Given a perfect binary tree, populate each node's next pointer to its immediate right neighbor on the same level (None at level's end). The follow-up is the question: constant extra space, which disqualifies the queue and forces a bootstrapping insight.

Input:  root = [1, 2, 3, 4, 5, 6, 7]
Output: level links 2->3, 4->5->6->7, and None at each level end

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Connect nodes per level screams BFS — but the O(1) constraint flips it: the next pointers you built on level k are the traversal structure for level k + 1. The output data structure replaces the queue. That bootstrapping is the entire insight.

The Approach

Walk the current level via next pointers, wiring children: each node's left child points to its right child, and its right child points to the next node's left child (when a next node exists). Then descend to the leftmost child and repeat.

Perfectness guarantees every internal node has both children, which is what makes the two wiring rules complete. The general-tree version (II) drops that guarantee and needs a dummy-head stitching loop — mention the difference explicitly.

Python Solution

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


def connect(root: Node | None) -> Node | None:
    """Wire next pointers level by level in O(1) space (perfect tree)."""
    leftmost = root
    while leftmost and leftmost.left:
        node = leftmost
        while node:
            node.left.next = node.right                    # within family
            node.right.next = node.next.left if node.next else None
            node = node.next
        leftmost = leftmost.left
    return root

Complexity

• Time: O(n) — each node is visited once as a parent and once as a child
• Space: O(1) — the next pointers being built serve as the queue

Interview Tips and Follow-Ups

• Lead with the queue version (O(w) space), then upgrade — showing the ladder is faster than guessing which rung the interviewer wants.
• Recursive solutions carry O(log n) stack — technically not O(1); saying so unprompted is a credibility deposit.
• For non-perfect trees (II): dummy head + tail stitching per level. Same bootstrapping idea, messier wiring — know it exists and how.

If this clicked, continue the Tree BFS arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.