117 · Populating Next Right Pointers in Each Node II

The O(1)-space level order: the level you have already linked is the queue for the next one. A dummy head plus a tail pointer removes every special case.

1 — The problem

Set each node's next pointer to the node immediately to its right on the same level, or null if there is none. The tree is arbitrary — not perfect — which is what separates this from LC 116, where root.left.next = root.right and the perfect shape does the rest.

A BFS with a queue solves it in O(n) time and O(width) space. The follow-up asks for constant extra space, and the observation that delivers it is this:

Once level k is fully linked, walking it via next visits exactly the nodes a queue would have held. The next pointers you just built are the queue — already allocated, inside the tree.

So the algorithm is two nested walks: an outer one that moves down one level at a time, and an inner one that traverses the current level horizontally, stitching the level below as it goes.

2 — Linking one level from the one above

Dashed horizontal lines are next pointers. Watch level 2 being walked left to right while level 3 is threaded onto tail behind it.

Node cur = root;while (cur != null) {    Node dummy = new Node(0), tail = dummy;    for (Node p = cur; p != null; p = p.next) {        if (p.left  != null) tail = tail.next = p.left;        if (p.right != null) tail = tail.next = p.right;    }    cur = dummy.next;}

Nothing is ever pushed or popped. The inner for walks pointers that the previous iteration of the outer while created, and the only variables are cur, dummy, tail and p.

2.1 What the dummy node buys you

Without it, the inner loop needs to distinguish "this is the first child I have found on the next level" from "this is a subsequent one", because the first must be remembered as the head while the rest are appended:

The dummy exists so that "the list is empty" and "the list has something in it" are the same code path. It is the same device used to simplify linked-list problems, and reallocating it fresh each level is what keeps dummy.next meaningful.

2.2 Why this is not O(width) in disguise

A fair objection: the level's nodes are all reachable at once, so is that not O(width) memory? No — the pointers holding them are next fields that the problem asked you to populate, and they belong to nodes that already exist. The auxiliary space is four pointers. Compare a queue-based BFS, which allocates an array holding up to n/2 references that the output does not need.

This same "reuse the structure you are building" idea appears in Morris traversal (LC 94) and in LC 114's O(1) version: when the output has pointer fields, they can double as scratch space.

3 — Complexity and edge cases

• Time O(n) — each node is visited once by the inner loop. Space O(1) auxiliary, versus O(width) for a queue-based BFS.
• Empty tree: the outer loop never runs; return null.
• Single node: next stays null, one outer iteration finds no children, dummy.next is null, done.
• Sparse levels — a node with only a right child, or gaps between subtrees — are handled without any special case, because the inner loop only appends the children that exist. This is exactly where LC 116's perfect-tree shortcut fails.
• Right-skewed tree: every level has one node, every next is null, and the outer loop runs h times.
• Common bug: allocating dummy once outside the outer loop. dummy.next then still points at the previous level's head and cur never advances — an infinite loop. Reset it, or reallocate.
• Common bug: advancing the inner loop with p = p.left or a child pointer instead of p.next. The horizontal walk is the whole mechanism.
• Common bug: reading cur = cur.left to descend. The next level's leftmost node is not necessarily the current leftmost node's child — that assumption is only valid on a perfect tree.

4 — Reference implementation

public Node connect(Node root) {
    Node cur = root;
    while (cur != null) {
        Node dummy = new Node(0);   // fresh every level
        Node tail = dummy;
        for (Node p = cur; p != null; p = p.next) {   // walk THIS level
            if (p.left  != null) tail = tail.next = p.left;
            if (p.right != null) tail = tail.next = p.right;
        }
        cur = dummy.next;              // head of the level just linked
    }
    return root;
}

The same code solves LC 116 — the perfect-tree version is strictly easier, not different. If you write this one, you never need to write that one.