Populate Next Right Pointers in a Binary Tree, in depth: queue BFS, O(1)-space level walking, the dummy-head trick and the traps in each

The problem, stated precisely

The node type is fixed by the problem. In Python it is a class with val, left, right and next, and next starts as null. You must return the root after setting every next. The usual serialisation prints each level left to right, following next, and ends each level with a #. So the perfect tree with values 1 to 7 must serialise as 1 # 2 3 # 4 5 6 7 #.

Pin down three details before writing any code. First, the rightmost node of every level must end up with next equal to null. Second, an empty tree is valid input and must return null. Third, the constant-space follow-up means O(1) extra memory beyond the tree. The output pointers don't count, because the problem requires them. A recursion stack does count, and that distinction decides which solutions actually meet the follow-up.

The mental model: every level becomes a linked list

After the algorithm runs, each depth of the tree is a singly linked list threaded through next, and its head is the leftmost node at that depth. A traversal that visits nodes in exactly that order is a level-order (breadth-first) traversal. So any correct BFS produces the right answer: link each node to the one dequeued after it within the same level.

The key observation is that a finished list at depth d already enumerates every node at depth d in left-to-right order. Their children, taken in the same order, are exactly the nodes at depth d+1 from left to right. So walking the list at depth d and emitting children builds the list at depth d+1 without any queue. The queue in BFS is doing the same job: holding one level's nodes in order. The next pointers can hold them instead. The picture resembles skip lists: stacked linked lists, one per level.

Baseline: breadth-first search with a queue

Start with the obviously correct version. It becomes the reference implementation for your tests later.

from collections import deque

def connect_bfs(root):
    if root is None:
        return root
    q = deque([root])
    while q:
        prev = None
        for _ in range(len(q)):          # exactly one level per outer iteration
            node = q.popleft()
            if prev:
                prev.next = node
            prev = node
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return root

Snapshotting len(q) before the inner loop is what separates levels. Children appended during the loop belong to the next level and are not counted. Because prev resets to null at the start of each level, the last node of a level is never linked to the first node of the next one, so the chain ends in null for free.

Time is O(n). Extra space is the maximum queue length, which equals the widest level. A perfect tree with n nodes has (n+1)/2 leaves, so the queue holds O(n) nodes. For a million-node tree that is half a million references kept alive at once. That cost is what the next two algorithms remove.

Perfect trees in O(1) space: sibling and cousin edges

In a perfect tree every next edge is one of two kinds, as the diagram shows. A sibling edge joins the two children of one parent. A cousin edge joins the right child of one parent to the left child of the parent's right neighbour. Standing on a parent, you can build the sibling edge immediately. The cousin edge needs parent.next. That pointer exists as long as you process levels top-down, because the previous pass built it.

def connect_perfect(root):
    leftmost = root
    while leftmost and leftmost.left:    # stop at the leaf level
        node = leftmost
        while node:                      # walk this level using links built last pass
            node.left.next = node.right                  # edge 1: siblings
            if node.next:
                node.right.next = node.next.left         # edge 2: cousins across parents
            node = node.next
        leftmost = leftmost.left
    return root

Two variables are the whole state: leftmost, the head of the level being walked, and node, the cursor. Since the tree is perfect, the head of the next level is always leftmost.left, and a node with a left child also has a right one, so neither dereference needs a guard. Extra space is O(1) and every node is touched a constant number of times, so time is O(n).

Worked trace on the tree 1..7

Follow the loop by hand once. It is the fastest way to believe the invariant: when the walk over depth d begins, depth d is fully linked.

Pass 2 depends on pass 1: 5.next = 6 was possible only because 2.next already pointed at 3. Any order that reaches depth 2 before depth 1 is linked silently leaves 5 pointing at null.

Arbitrary trees: the dummy-head technique

The general version breaks both assumptions the perfect-tree loop relied on. The next level's head is no longer leftmost.left, since the leftmost node may have no children at all. And a node's right neighbour may be any number of positions away, past parents with no children. The fix is to stop reasoning about edge kinds and build the next level as a plain linked list with a sentinel.

def connect_any(root):
    head = root                          # first node of the level being walked
    while head:
        dummy = Node(0)                  # sentinel in front of the next level
        tail = dummy
        node = head
        while node:
            if node.left:
                tail.next = node.left
                tail = tail.next
            if node.right:
                tail.next = node.right
                tail = tail.next
            node = node.next
        head = dummy.next                # None when the level below is empty
    return root

Walk the current level through its next links and append each existing child to a list whose tail you track. The sentinel removes the special case for the first child found, and dummy.next gives you the next level's head without searching. When a level has no children, dummy.next stays null and the loop ends. One sentinel is allocated per level, which is O(1) live memory. To avoid even that allocation, keep a next_head variable set the first time a child is found.

Trace it on a ragged tree: root 1; children 2 and 3; then 4 and 5 under 2, only a right child 7 under 3; then 8 under 4 and 9 under 7. Walking level 2 (4, 5, 7) appends 8, skips 5, and appends 9, which yields 8 → 9. Here two leaves are linked across two missing subtrees, which is the case where the perfect-tree loop would fail. Running this code, the queue version and the perfect-tree version on these inputs gave identical levels, including on a single node and on null.

Recursive versions and why they trip people up

For perfect trees a short recursion works: set root.left.next = root.right, set root.right.next = root.next.left if root.next exists, then recurse left and right. Preorder is enough, because a parent always sets its children's links before recursing into them. Keep in mind that this uses O(h) stack, which is O(log n) for a perfect tree, so it doesn't meet the strict constant-space follow-up. Interviewers who ask for O(1) usually mean the iterative walk.

For arbitrary trees, recursion has a nastier trap. A typical attempt finds a child's neighbour by scanning root.next, root.next.next and so on for the first node with a child. That scan reads next pointers on the parent's level to the right. If you recurse into the left subtree first, those pointers on the right-hand side may not exist yet at deeper levels, and the scan stops early. The result is correct on small tests and wrong on deep, ragged trees. The fix is to recurse right first, so the right side of every level is linked before the left side needs it. Better still, use the iterative dummy-head loop, which avoids both the ordering subtlety and the stack cost.

The same algorithms in Java

In Java the same algorithm uses Node with public fields. The general-tree version is shown because it also handles perfect trees correctly.

class Solution {
    public Node connect(Node root) {
        Node head = root;
        Node dummy = new Node(0);            // reused across levels
        while (head != null) {
            dummy.next = null;
            Node tail = dummy;
            for (Node cur = head; cur != null; cur = cur.next) {
                if (cur.left != null)  { tail.next = cur.left;  tail = tail.next; }
                if (cur.right != null) { tail.next = cur.right; tail = tail.next; }
            }
            head = dummy.next;
        }
        return root;
    }
}

Reusing one sentinel removes the per-level allocation, but only with the reset at the top of each level. Without it, the last level sees a stale dummy.next and the loop never ends.

Complexity side by side

The O(n) bounds for the walks hold because each node is appended once and visited once as a cursor; the Big-O guide covers this style of counting. The scanning recursion is linear too: each scan stops at the next parent with children, so the spans scanned on one level do not overlap.

Testing: invariants and a differential check

Two checks catch almost every bug. The invariant check walks each level through next and compares it to a BFS listing of the same level. The differential check generates random trees, clones each one, runs the queue version on one copy and the constant-space version on the other, and compares the serialisations.

def serialise(root):
    out, head = [], root
    while head:
        nxt, cur = None, head
        while cur:
            out.append(cur.val)
            nxt = nxt or cur.left or cur.right
            cur = cur.next
        out.append("#")
        head = nxt
    return out

In serialise, the next level's head is the first child found while walking the current level. That is correct only if the links are right, so it doubles as a check. Include the edge cases explicitly: null, one node, a left-only chain, a right-only chain, and a wide shallow tree.

Where level links appear in real systems

Sibling pointers are not just a puzzle. B+ trees link their leaves so a range scan can move sideways without climbing back up. Lehman and Yao's B-link tree goes further and adds a right link at every level, letting concurrent readers recover when a split moves keys to a new right sibling under them. The LSM versus B-tree comparison explains why those sideways scans matter for storage engines.

There is also an arithmetic version. A perfect tree stored in an array in 1-indexed heap layout puts depth k at indices 2^k through 2^(k+1)-1. So node i's next is simply i+1, unless i+1 is a power of two, in which case it is null. Implicit trees such as the segment tree get level adjacency for free this way. The pointer algorithms here are what you need when the tree is irregular and lives on the heap.

Failure modes to check in review

• The rightmost node of a level points at the next level's first node, because the BFS never reset prev between levels.
• The perfect-tree loop is applied to an arbitrary tree, which crashes on node.left.next when a left child is missing.
• A recursive general-tree solution recurses left first, so deep ragged trees come out with missing links.
• The reused sentinel is never cleared, which makes the loop run forever.
• Null root input is not handled, so the code throws before reaching the loop.
• Output is checked only by BFS order, never by following next itself, so wrong links pass the test.

What to do next

1. Implement the queue BFS and keep it as the reference.
2. Write the perfect-tree parent walk from memory, then trace it on 1..7 using the table above.
3. Implement the dummy-head walk and run the ragged example with 8 and 9 on the bottom level.
4. Add the random differential test and run it on a few thousand trees.
5. Write the recursive general-tree version left-first, find a failing tree, then fix it by recursing right first.
6. Port the dummy-head version to Java with a reused sentinel and confirm the reset is there.