Populating Next Right Pointers: Level-by-Level Linking

Given a perfect binary tree where all leaves are on the same level and every parent has two children, populate each node's next pointer to point to its next right node. If there is no next right node, the next pointer should be set to null. Initially, all next pointers are set to null. This is LeetCode 116: Populating Next Right Pointers in Each Node.

For example, given root = [1, 2, 3, 4, 5, 6, 7], after connecting the next pointers, node 2 points to node 3, node 4 points to node 5, node 5 points to node 6, and node 6 points to node 7. The rightmost node on every level points to null.

Approach

You could solve this with BFS using a queue, processing each level and linking nodes left to right. That works, but it uses O(n) space for the queue. Since the tree is perfect, you can do better: O(1) extra space.

The key insight is that once you have linked a level with next pointers, you can traverse that level horizontally without a queue. You use the already-established next pointers from the parent level to walk across and link the child level.

For each node on the current level:

1. Link left child to right child: node.left.next = node.right. This connects siblings under the same parent.
2. Link across subtrees: if node.next exists, then node.right.next = node.next.left. This bridges the gap between two different parents on the same level.

After linking all children of the current level, move down one level by following leftmost = leftmost.left. Since the tree is perfect, the leftmost node on any level always has a left child (until you reach the leaf level).

The Python solution

def connect(root):
    if not root:
        return root
    leftmost = root
    while leftmost.left:
        node = leftmost
        while node:
            node.left.next = node.right
            if node.next:
                node.right.next = node.next.left
            node = node.next
        leftmost = leftmost.left
    return root

Here is what each part does:

• leftmost = root tracks the first node of the current level. You always start at the leftmost node so you can walk the entire level.
• while leftmost.left is the outer loop. It stops when leftmost is a leaf node (no children to link). In a perfect binary tree, if a node has no left child, it has no right child either.
• node = leftmost starts the inner traversal at the beginning of the current level.
• node.left.next = node.right links the two children of the same parent. This is always valid because the tree is perfect.
• node.right.next = node.next.left links across subtree boundaries. If node.next exists, the right child of the current node connects to the left child of the next node on the same level.
• node = node.next moves horizontally to the next node on the current level using the next pointer that was established when this level was the child level.
• leftmost = leftmost.left drops down one level after all children on the current level have been linked.

Visual walkthrough

Trace through the tree [1, 2, 3, 4, 5, 6, 7]. Watch how each level's next pointers are established by traversing the level above.

Notice the two types of links at each step. The within-parent link (node.left.next = node.right) is always present. The cross-parent link (node.right.next = node.next.left) only fires when node.next is not null. Together, they stitch every level into a complete linked list.

Complexity analysis

The O(1) space is what makes this solution elegant. A BFS queue-based approach would use O(n) space because the widest level of a perfect binary tree holds n/2 nodes. By leveraging the next pointers you have already set, you replace the queue with the tree's own structure.

Building blocks

This problem is built on one core pattern: level-by-level linking using already-established pointers.

leftmost = root
while leftmost.left:
    node = leftmost
    while node:
        node.left.next = node.right
        if node.next:
            node.right.next = node.next.left
        node = node.next
    leftmost = leftmost.left

The outer loop drops one level at a time. The inner loop walks the current level horizontally using next pointers, linking children as it goes. This is a form of level-order traversal without a queue, made possible by the fact that the previous level is already fully linked.

This pattern reappears in any problem where you need to traverse a tree level by level with constant space. The trick is always the same: use the structure you have already built (next pointers on the parent level) to avoid auxiliary data structures.

Edge cases

• Empty tree (root is None): return None. The guard clause at the top handles this.
• Single node (no children): leftmost.left is None, so the outer loop never runs. The root's next stays null, which is correct.
• Two levels (root with two children): the outer loop runs once. It links root.left.next = root.right and stops. No cross-subtree link is needed because root.next is null.

From understanding to recall

You just traced through an O(1) space solution that links each level using the pointers already established on the level above. The two linking rules (within-parent and cross-parent) feel natural now. But in two weeks, will you remember that the outer loop checks leftmost.left and not leftmost? Will you recall which pointer goes to node.next.left versus node.next.right?

Reading is not the same as reproducing under pressure. Spaced repetition bridges that gap. You type the level-by-level linking template from memory at increasing intervals: first after a day, then three days, then a week. Each repetition cements the two linking rules and the leftmost descent until the pattern becomes automatic.

Level-by-level linking is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Level Order Traversal - The BFS queue-based approach to level-order processing that this problem replaces with O(1) space
• Binary Tree Zigzag Level Order Traversal - Another level-order variant that adds a direction flag to alternate traversal order