Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Each node in a perfect binary tree has an extra next pointer. The task is to make that pointer lead to the node immediately to its right on the same level, or to None when the node is the level’s last one.

The tree is perfect: every internal node has exactly two children and all leaves share the same depth. A breadth-first traversal can solve the problem with a queue, but the more interesting requirement is to use only constant extra space.

Deriving the constant-space solution

Look at one parent on a level whose next pointers are already correct. There are only two connections to make beneath it. Its left child points to its right child. Its right child points to the left child of the parent’s neighbor, if that neighbor exists.

That second connection explains why the tree must be processed from top to bottom. The finished next chain on the current level acts like a free linked list: it lets the algorithm move horizontally from parent to parent without a queue. While doing so, the algorithm constructs the complete chain for the level below. It then drops to the leftmost child and repeats.

The root is already a one-node chain, so it provides the base case. At every later level, sibling connections cover pairs within one parent, while cross-parent connections bridge consecutive pairs. Together they connect every adjacent pair of nodes exactly once.

Why the algorithm works

Before an outer-loop iteration begins, assume the current level is linked correctly from left to right and ends at None. This is initially true for the root.

Walking through that chain visits every parent on the level. For each parent, connecting its left child to its right child establishes the only adjacency inside the parent’s subtree. If another parent follows, connecting the right child to that next parent’s left child establishes the only adjacency between the two subtrees. The final parent’s right child is set to None, so the new chain has the correct ending as well.

The entire next level is therefore linked correctly. By induction, every level is correct when the traversal finishes.

Complexity

Every internal node is visited once while its children’s pointers are assigned, so the running time is O(n). The algorithm stores only a few node references, giving O(1) auxiliary space. The next pointers themselves are part of the required output and do not count as extra storage.

Python solution

from __future__ import annotations


class Node:
    """A node in a binary tree with a horizontal neighbor pointer."""

    __slots__ = ("val", "left", "right", "next")

    def __init__(
        self,
        value: int = 0,
        left: Node | None = None,
        right: Node | None = None,
        next_node: Node | None = None,
    ) -> None:
        self.val = value
        self.left = left
        self.right = right
        self.next = next_node


class PerfectTreeConnector:
    """Populate horizontal links in a perfect binary tree."""

    @classmethod
    def connect(cls, root: Node | None) -> Node | None:
        """Connect each node to its next node on the same level in place."""
        if root is None:
            return None

        # Clear a possibly stale value and establish the first level's chain.
        root.next = None
        leftmost_parent = root

        while leftmost_parent.left is not None:
            cls._connect_child_level(leftmost_parent)
            leftmost_parent = leftmost_parent.left

        return root

    @staticmethod
    def _connect_child_level(leftmost_parent: Node) -> None:
        """Build one child-level chain from an already linked parent level."""
        parent: Node | None = leftmost_parent

        while parent is not None:
            # A perfect tree guarantees that every non-leaf has both children.
            left_child = parent.left
            right_child = parent.right
            if left_child is None or right_child is None:
                raise ValueError("Expected a perfect binary tree.")

            # Join siblings under the same parent.
            left_child.next = right_child

            # Bridge neighboring subtrees, or terminate the level explicitly.
            right_child.next = (
                parent.next.left if parent.next is not None else None
            )
            parent = parent.next


class Solution:
    """LeetCode-compatible entry point."""

    def connect(self, root: Node | None) -> Node | None:
        return PerfectTreeConnector.connect(root)

Interview follow-ups

What changes if the binary tree is not perfect?

Use the current level’s completed next chain to scan horizontally, but build the next level through a dummy head and a tail pointer. Append each non-null left and right child to the tail in encounter order. When the scan ends, the dummy head identifies the next level’s first node.

This is the standard constant-space solution to the more general problem because it never assumes that a sibling or a neighboring parent’s left child exists. Every node is appended once, so the running time remains O(n) and the auxiliary space remains O(1). The tradeoff is slightly more pointer bookkeeping than the perfect-tree-specific solution.

How would a breadth-first solution work?

Place the root in a queue and process one queue length at a time. Within each level, point every node to the next node removed from that same batch, and set the last node’s pointer to None. Enqueue non-null children for the following level.

Level-sized batches directly match the definition of the required links, which makes this approach easy to explain and adapt to arbitrary binary trees. It still takes O(n) time, but the queue can hold O(w) nodes, where w is the tree’s maximum width. A perfect tree can have w = O(n), so it does not meet the constant-space target.

Can the perfect-tree solution be written recursively?

Yes. For each node, connect its left child to its right child. If the node has a neighbor, connect its right child to that neighbor’s left child. Then recurse into the left and right subtrees. The parent level must be connected before these recursive calls so cross-subtree neighbors are available when needed.

The same sibling and cross-parent argument proves correctness, and every node still requires constant work, giving O(n) time. The call stack uses O(h) space. Because a perfect tree has height O(log n), this is modest, but it is not the strict O(1) auxiliary space achieved by the iterative version.

What if the input may contain stale next pointers?

The algorithm should not trust the root’s existing pointer or leave the last node of a level untouched. Clear root.next before beginning, and explicitly assign None to the final right child on every generated level. The implementation does both through the conditional cross-parent assignment.

As a result, all output pointers depend only on the tree structure. Running the method repeatedly produces the same links, so the operation is idempotent. These assignments do not change the O(n) time or O(1) space bounds.

How would you verify that the input really is a perfect binary tree?

Traverse the tree while tracking depth. Every internal node must have exactly two children, and every leaf must occur at the same depth. A depth-first validator can remember the depth of the first leaf and compare all later leaves against it; encountering a node with exactly one child fails immediately.

Validation takes O(n) time. Recursive depth-first search uses O(h) call-stack space, while breadth-first search uses O(w) queue space. That creates a deliberate production tradeoff: strict validation sacrifices the connector’s constant-space guarantee, so an interview solution normally relies on the stated perfect-tree precondition and keeps validation separate.

Once one level’s next chain exists, different parents on that level can conceptually assign their children’s two outgoing links independently because each assignment writes to a distinct child. A barrier is still required before workers descend, since the next level must be fully linked before it can guide horizontal traversal.

The total work remains O(n), and a balanced tree exposes substantial work on its wider levels. In practice, the operations are so small that scheduling and synchronization usually cost more than the pointer assignments. Parallelism becomes reasonable only when connecting a node also performs substantial application-specific work.