Populating Next Right Pointers II: Handling Non-Perfect Trees

Given a binary tree where each node has a left, right, and next pointer, populate each next pointer to point to the node immediately to its right on the same level. If there is no right neighbor, set next to null.

This is LeetCode 117: Populating Next Right Pointers in Each Node II. Unlike LeetCode 116, the tree is not necessarily perfect. Any node might be missing its left child, right child, or both. You need to handle all of these cases while using only O(1) extra space.

Why this is harder than the perfect-tree version

In a perfect binary tree, every node has exactly two children and every level is full. That means the next-level connections follow a predictable pattern: node.left.next = node.right, and node.right.next = node.next.left. You can hardcode these two rules.

With an arbitrary binary tree, that pattern breaks. A node might have only a left child, only a right child, or no children at all. When you need to find the "next right" child on the next level, you might have to skip across multiple parents that have no children on the relevant side. The simple two-rule approach no longer works.

The solution is a dummy-node technique that builds the next level's linked list from scratch as you traverse the current level.

The approach: dummy node linked list construction

The idea is to process the tree level by level, but instead of using a queue (which costs O(n) space), you use the next pointers you have already built on the current level to traverse it. For the next level, you use a dummy node as the head of a temporary linked list:

1. Create a dummy node. It acts as a placeholder head for the next level's linked list.
2. Use a tail pointer, starting at dummy, to append children as you find them.
3. Walk curr across the current level using next pointers.
4. For each curr, if it has a left child, set tail.next = curr.left and advance tail. If it has a right child, set tail.next = curr.right and advance tail.
5. When curr reaches null (end of the current level), the next level starts at dummy.next. Reset dummy.next = null, reset tail = dummy, and set curr = dummy.next from the previous iteration.

The dummy node solves the "which child comes first on the next level?" problem. You do not need to know in advance whether the first child is a left or right child, or which parent it belongs to. You just append every child you find, in left-to-right order, to the tail of the linked list.

Python solution

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

def connect(root):
    curr = root
    while curr:
        dummy = Node(0)
        tail = dummy
        while curr:
            if curr.left:
                tail.next = curr.left
                tail = tail.next
            if curr.right:
                tail.next = curr.right
                tail = tail.next
            curr = curr.next
        curr = dummy.next
    return root

Visual walkthrough

Let's trace through the tree [1, 2, 3, 4, 5, null, 7]. Watch how the dummy node builds each level's linked list as curr walks across the current level via next pointers.

The critical moment is Step 4. When curr moves from node 2 to node 3 (via the next pointer built in the previous iteration), the tail pointer has already linked 4 and 5. Node 3 has no left child, so it only contributes its right child (7). The tail links 5 to 7, bridging across two different parents. That is the power of the dummy node: it does not care which parent a child belongs to.

How the code works, line by line

The outer while curr loop runs once per level. At the start of each iteration, curr is the first node on the current level (the root for Level 0, then dummy.next for each subsequent level).

Inside, the inner while curr loop walks across the current level using next pointers. For each node, it checks for left and right children and appends them to the tail of the next-level linked list. The tail.next = curr.left and tail.next = curr.right lines are the same operation: "append this child to the end of the list and advance tail."

When the inner loop finishes, dummy.next points to the first node on the next level. Setting curr = dummy.next drops down one level and starts the process again. If dummy.next is null, there are no more levels, and the outer loop ends.

The dummy node is reset each time the outer loop iterates, because a new dummy = Node(0) is created at the top of the loop. This keeps the solution clean: each level gets its own fresh dummy.

Complexity analysis

Time: O(n). Every node is visited exactly once as curr on its level. Each child link operation is O(1). Total work is proportional to the number of nodes.

Space: O(1). The only extra memory is the dummy node and the tail/curr pointers. No queue, no recursion stack. The next pointers are part of the output, not extra space.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. Dummy-head linked list construction

The pattern of using a dummy node to simplify linked list building:

dummy = ListNode(0)
tail = dummy
while condition:
    tail.next = new_node
    tail = tail.next
return dummy.next

You see this pattern in Merge Two Sorted Lists, Partition List, and any problem where you are building a linked list without knowing the head in advance. The dummy node removes the "is this the first node?" check and lets you always use tail.next = ... uniformly.

2. Level traversal via next pointers

The pattern of walking across a level using the next pointers you have already set:

curr = level_start
while curr:
    process(curr)
    curr = curr.next

This replaces a BFS queue with O(1) space traversal. You can only use this pattern when the current level already has its next pointers wired up, which is exactly what the previous iteration accomplished. This is the same traversal used in Populating Next Right Pointers, and it generalizes to any problem where a prior pass has linked nodes into a traversable list.

Edge cases

• Empty tree: root is null. The outer while curr never executes, and we return null. No special check needed.
• Single node: the root has no children. The inner loop runs once, finds no children, so dummy.next is null. The outer loop ends after one iteration. The root's next stays null.
• All nodes on one side (skewed tree): every node has only a left child (or only a right child). The dummy node handles this naturally. Each level has exactly one node, and each node's next is null. The dummy just links each single child as the sole member of the next level.

From understanding to recall

You understand the dummy-node technique. You see how tail builds the next-level list while curr walks the current level. The logic is clean. But under interview pressure, the nesting of two while loops, the dummy reset, and the curr = dummy.next handoff are easy to fumble.

The details that trip people up: creating a fresh dummy inside the outer loop (not before it), using tail to append (not dummy), and remembering that curr = dummy.next is how you drop to the next level. These are mechanical things that spaced repetition makes automatic.

You practice writing the two-loop structure from scratch at increasing intervals. After a few rounds, the dummy-node pattern flows naturally. You do not need to re-derive the approach. You just write it.

Related posts

• Populating Next Right Pointers in Each Node - The perfect-tree version (LeetCode 116), where next-pointer rules are simpler because every level is full
• Binary Tree Level Order Traversal - The BFS queue approach to level-by-level processing, which this problem optimizes to O(1) space

CodeBricks breaks this problem into its dummy-head linked list construction and level-traversal-via-next-pointers building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the two-loop dummy-node pattern is automatic. When you hit any tree-linking problem in your interview, you do not think about it. You just write it.