105. Populating Next Right Pointers in Each Node II

Once a level is fully linked by next pointers, it behaves exactly like a linked list — you can walk it left to right without any queue. So process the tree one level at a time: while walking the current (already-linked) level, thread its children into the next level using a dummy head. This reuses the next pointers instead of a BFS queue, so the extra space is O(1).

Why the perfect-tree trick doesn't directly apply

In a perfect binary tree every node has two children, so node.left.next = node.right and the wiring is mechanical. Here the tree is arbitrary — a node may have only a left child, only a right child, or none — so we can't assume where the next node on a level lives. We need a method that adapts to gaps.

Treat each level as a linked list

The key insight: after a level's next pointers are set, that level is a singly linked list. We can traverse it left to right with just a pointer — no queue, no recursion over the whole tree. While traversing level k, we build level k+1's next chain.

To build the child chain cleanly, use a dummy head: a throwaway node whose next will point to the first node of the next level. Keep a tail pointer starting at the dummy. As we walk the current level, for each node we append its existing children (left then right, skipping nulls) to tail:

• tail.next = child; tail = child.

When the current level is exhausted, dummy.next is the leftmost node of the next level, already linked. Move down and repeat.

Algorithm

1. head = root (the leftmost node of the current level).
2. While head is not null:
   • Create a fresh dummy; set tail = dummy.
   • Walk the current level via next, starting at head. For each node, append node.left then node.right (if non-null) to tail.
   • Set head = dummy.next (leftmost of the next level).
3. All next pointers are now set. (For verification we also collect each level's values while walking it.)

Worked example: root = [1,2,3,4,5,null,7]

• Level [1]: dummy threads 1's children → 2 → 3. head = 2.
• Level [2,3]: walk 2 → 3. Node 2 appends 4, 5; node 3 has no left, appends 7. Chain: 4 → 5 → 7. head = 4.
• Level [4,5,7]: no children. dummy.next = null, so head = null; stop.

The next pointers now read 1, then 2 → 3, then 4 → 5 → 7 — including the cross-parent link 5 → 7. Collected: [[1],[2,3],[4,5,7]].

Complexity

• Time: O(n) — each node is visited a constant number of times.
• Space: O(1) extra — only the dummy and a few pointers; we walk levels through the next pointers rather than a queue.

import java.util.*;

class Solution {
    // Returns each level's values read left-to-right by following the next
    // pointers we set — proving the wiring is correct. TreeNode carries a `next`
    // field supplied by the harness.
    public List<List<Integer>> connect(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        TreeNode head = root;
        while (head != null) {
            List<Integer> vals = new ArrayList<>();
            for (TreeNode n = head; n != null; n = n.next) vals.add(n.val);
            result.add(vals);

            TreeNode dummy = new TreeNode(0), tail = dummy;
            for (TreeNode n = head; n != null; n = n.next) {
                if (n.left != null) { tail.next = n.left; tail = tail.next; }
                if (n.right != null) { tail.next = n.right; tail = tail.next; }
            }
            head = dummy.next;
        }
        return result;
    }
}