Populating Next Right Pointers in Each Node

The queue-based solution is easy to see. The constant-space solution is easier to miss: once one level is connected, its next pointers become the queue for the next traversal.

Read the contract before choosing the traversal

This problem gives you a perfect binary tree:

• Every internal node has both a left and a right child.
• Every leaf appears at the same depth.
• Each node also has a next pointer.
• A node's next pointer must point to the next node on the same level, or remain None for the rightmost node.

The child relationships must stay unchanged. Only the horizontal next links are populated, and the function returns the original root.

For the tree:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

the result is:

1 -> None
2 -> 3 -> None
4 -> 5 -> 6 -> 7 -> None

The values do not drive the algorithm. The tree shape does.

Two boundary cases should already be in your mental test suite:

• root is None: there is nothing to connect.
• A single-node tree: the root has no same-level neighbor, so root.next remains None.

The perfect-tree condition is the decisive clue. Without it, a node's next parent may not have a left child. With it, every non-leaf parent has exactly the two children the algorithm expects.

Recognize the pattern: the tree already contains a level list

The problem asks about same-level neighbors, so a traversal that understands levels is the natural starting point.

A straightforward breadth-first search uses a queue:

1. Put the root in the queue.
2. Process one level at a time.
3. Connect each node to the next node removed from that level.
4. Enqueue the children for the next level.

This is a good baseline. It makes the output contract obvious and uses O(w) auxiliary space, where w is the maximum width of the tree.

But the follow-up asks for constant extra space. The queue is storing information the tree can eventually store for us.

After connecting a parent level, its nodes form a linked list through next:

parent 1 -> parent 2 -> parent 3 -> None

We can walk that list directly. While walking it, we build the linked list for the child level.

That gives the central reframe:

The current level is already a traversal spine. Use its next links instead of allocating a queue.

For each parent, there are exactly two connections to create:

1. Connect its own children:

   parent.left.next = parent.right
   

2. Connect across the boundary between adjacent parents:

   parent.right.next = parent.next.left
   

The second assignment is the one candidates commonly omit. It connects the right subtree of one parent to the left subtree of the next parent.

For example:

        parent A --------> parent B
        /      \           /      \
   A.left   A.right    B.left   B.right

The child-level order is:

A.left -> A.right -> B.left -> B.right

The first link comes from one parent. The middle link crosses between parents. The last link comes from the next parent.

This shortcut depends on the perfect-tree contract. In an arbitrary binary tree, parent.next.left might not exist. That is a different problem with a more general linking strategy.

Decompose the pointer work into two obligations

It helps to separate traversal state from connection logic.

Obligation 1: connect siblings

For every parent with children:

parent.left.next = parent.right

This handles adjacent children under the same parent.

Obligation 2: connect neighboring subtrees

If the parent has a neighbor on the same level:

parent.right.next = parent.next.left

This handles the boundary between two consecutive parent subtrees.

The algorithm needs two pointers:

• leftmost: the first node on the current parent level.
• current: the node currently being visited across that level.

At the beginning of an outer-loop iteration, leftmost identifies the level we will walk. The next chain from leftmost lets current visit every parent on that level.

After processing the level, the first child of leftmost is the first node of the next level:

leftmost = leftmost.left

That assignment is safe because the tree is perfect. If leftmost has a child, it has both children.

The rightmost child on the new level should point to None. Since the problem initializes next pointers to None, we do not assign a link after the final child. The constructed chain ends naturally.

Derive the constant-space algorithm

The algorithm is a small state machine:

1. Start leftmost at the root.
2. Stop when the current level has no children.
3. Walk that level using current = current.next.
4. Connect each parent's two children.
5. If a neighboring parent exists, bridge the two subtrees.
6. Move leftmost down to the next level.
7. Return the original root.

Pseudocode:

leftmost = root

while leftmost exists and leftmost has a left child:
    current = leftmost

    while current exists:
        current.left.next = current.right

        if current.next exists:
            current.right.next = current.next.left

        current = current.next

    leftmost = leftmost.left

return root

Notice what is doing the work:

• Child pointers move downward.
• next pointers move sideways.
• leftmost marks the start of a level.
• current scans the already-built horizontal chain.

The algorithm never searches for a same-level neighbor. It has already built the path that identifies that neighbor.

The invariant and correctness

The key loop invariant is:

At the start of each outer-loop iteration, every node on the current level is connected from left to right through next, and leftmost points to the first node on that level.

The root level satisfies the invariant immediately. It contains one node, and its next pointer is None.

Now assume the invariant holds for the current parent level. The inner loop visits parents from left to right because it follows their established next chain.

For each parent:

1. current.left.next = current.right connects the two children under that parent.
2. If current.next exists, current.right.next = current.next.left connects the current parent's right child to the next parent's left child.

Those are the only two types of adjacency in the next level of a perfect binary tree:

same parent:       left -> right
neighboring parent: right -> next parent's left

Because parents are processed from left to right, these assignments create the child chain in left-to-right order. The final parent has no current.next, so its right child receives no outgoing assignment and remains the rightmost node with next = None.

Finally, leftmost.left is the first node of the newly constructed child level. Therefore the invariant holds for the next outer-loop iteration.

At the leaf level, leftmost.left is None, so the loop stops. No leaf has children to connect, and every level has the required horizontal links.

That is the proof. The code is short because the tree's structure carries most of the state.

Dry-run on a three-level tree

Start with:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

Initially, all next pointers are None.

Process level 1

leftmost = 1 and current = 1.

Node 1 has children 2 and 3:

2.next = 3

Node 1 has no next neighbor, so there is no cross-parent assignment.

The next level is now:

2 -> 3 -> None

Move down:

leftmost = leftmost.left  # leftmost = 2

Process level 2

The inner loop follows the existing chain:

current = 2
current.next = 3

For parent 2:

4.next = 5
5.next = 6

The first assignment connects siblings. The second crosses from parent 2 to parent 3.

For parent 3:

6.next = 7

Parent 3 has no neighbor, so 7.next remains None.

The completed child level is:

4 -> 5 -> 6 -> 7 -> None

A compact trace looks like this:

Current parent	Assignment	Resulting child link
1	2.next = 3	2 -> 3
2	4.next = 5	4 -> 5
2 with 2.next = 3	5.next = 6	5 -> 6
3	6.next = 7	6 -> 7
3 has no neighbor	no assignment	7 -> None

Now leftmost becomes 4. Since 4 has no children, the outer loop stops.

For an empty tree, the loop does not run. For a single-node tree, leftmost.left is already None, so the root is returned unchanged.

Populating Next Right Pointers in Each Node Python implementation

The Python implementation should make the two obligations visible rather than compressing them into clever pointer manipulation.

class Solution:
    def connect(self, root: "Node | None") -> "Node | None":
        if root is None:
            return root

        leftmost = root

        # Process each level that has a child level below it.
        while leftmost.left is not None:
            current = leftmost

            # Walk the current level through its established next links.
            while current is not None:
                # Obligation 1: connect children of the same parent.
                current.left.next = current.right

                # Obligation 2: connect across adjacent parent subtrees.
                if current.next is not None:
                    current.right.next = current.next.left

                current = current.next

            # In a perfect tree, the first left child starts the next level.
            leftmost = leftmost.left

        return root

The early return handles root = None. The outer condition avoids processing a leaf level, where there are no children to connect.

The inner loop depends on a previously established fact: every node on the current level is reachable through next. That is why the algorithm must process levels from top to bottom. You cannot use a horizontal chain before building it.

A recursive solution can express the same relationships, but it consumes call-stack space proportional to the tree height. The iterative version exposes the constant-space follow-up directly and keeps the traversal state in the links already attached to the tree.

Complexity, edge cases, and failure modes

Let n be the number of nodes.

Time complexity

The algorithm runs in O(n) time.

Each node is visited once as current on its parent level. During that visit, it performs a constant amount of pointer work:

• One sibling connection.
• At most one cross-parent connection.
• One move to current.next.

The work is linear in the number of nodes.

Auxiliary space complexity

The algorithm uses O(1) auxiliary space.

It stores only leftmost and current; it does not allocate a queue, list of nodes, or per-level buffer. The next pointers inside the input structure provide the horizontal traversal paths.

A queue-based BFS is also O(n) time, but its auxiliary space is O(w), where w is the widest level. That baseline is often the right first implementation when you are validating the problem contract. The linked-level version is the sharper answer when constant extra space matters.

Edge cases to check

• Empty tree: return None.
• Single node: return the root with next = None.
• Two-level tree: connect the root's left child to its right child.
• Three-level tree: verify the cross-subtree bridge, such as 5.next = 6.
• Rightmost node on every level: its next must remain None.
• Duplicate values: links must be based on node references, not values. Values are irrelevant.

Common mistakes

Forgetting the cross-parent bridge

This assignment is essential:

current.right.next = current.next.left

Without it, each pair of siblings is connected, but separate subtrees remain disconnected:

4 -> 5    6 -> 7

The required result is:

4 -> 5 -> 6 -> 7

Confusing next with a child pointer

current.next points sideways to the next parent on the same level. It is not the next node in a depth-first traversal, and it is not one of the current node's children.

Moving down through an arbitrary child

This transition is valid here:

leftmost = leftmost.left

It relies on the perfect-tree guarantee. In a sparse binary tree, leftmost.left could be missing even when a lower level still exists. The general variant requires finding the next available child across the horizontal chain.

Connecting across levels

Every assignment must connect nodes that belong to the same child level. The parent chain controls which subtrees are adjacent. Do not use a parent itself as a target for a child-level link.

Forgetting to return the root

The function mutates the tree in place, but the expected result is still the root object:

return root

The transferable recognition rule

When a tree problem asks for same-level relationships, start with level order. Then inspect the structure before reaching for a queue.

For a perfect binary tree, the parent level can become a linked list through next. That list replaces the queue:

Walk the known horizontal chain. Build the next horizontal chain. Move down.

Before submitting, verify five things:

1. The empty-root guard exists.
2. Siblings are connected.
3. The cross-parent bridge is connected.
4. The rightmost node on each level ends at None.
5. The original root is returned.

That is the durable pattern behind this Populating Next Right Pointers in Each Node solution: when the structure gives you an ordered traversal path for free, use it as working memory instead of rebuilding the same information in a separate data structure.