Populating Next Right Pointers in Each Node II

Given a binary tree (not necessarily perfect), connect each node's Next pointer to its next right node in the same level. If there is no next right node, set Next to nil. Return the root.

Why this is worth learning

Sparse trees require linking the actual nodes present at each level, not assuming every parent has two children. Existing Next pointers are output fields and cannot be trusted as traversal input in the queue reference.

Before coding: one-minute experiment

Why must the last node’s Next be set to nil even when a newly built tree would already have nil there?

Function signature

func Connect(root *Node) *Node

Inputs / outputs

• root: root of the tree.
• Return: root, after linking Next pointers.

Example

    1
   / \
  2   3
 / \   \
4   5   7

Level links:
1 -> nil
2 -> 3 -> nil
4 -> 5 -> 7 -> nil

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

A depth-indexed collection can identify every node's same-level successor, but a queue can build those links as the level is read. Keep the previous popped node and link it to the current node. At the end, explicitly set the last Next to nil. Existing Next fields are untrusted output state and may contain self-cycles, so the reference discovers through Left/Right only. An alternative constant-auxiliary-space method can traverse established Next chains, but must first make each current chain correct before trusting it.

Invariant: nodes popped in the same BFS layer are in left-to-right order, so you can chain Next pointers linearly.

Algorithm (step-by-step)

1. If root is nil, return nil.
2. Push root into a queue.
3. While queue not empty:
   • Let n be the level size.
   • Pop the first node as prev.
   • For the remaining n-1 nodes, pop cur, set prev.Next = cur, then advance prev = cur.
   • Assign nil to the last node's Next, replacing any stale link.
   • Enqueue children of each popped node as you go.
4. Return root.

Correctness sketch

BFS forms the exact left-to-right node sequence for one level. Link each previously removed node's Next to the current node, then set the final node's Next to nil. These assignments create precisely the successor relation within that level and no cross-level edge. Child discovery uses Left and Right pointers, so stale or cyclic initial Next values cannot corrupt traversal. Repeating for every frozen-size level sets every Next field to its required value, including terminal nils, while preserving the root, node identities, child edges, and values.

Trace (hand walkthrough)

Example input:
    1
   / \
  2   3
 / \   \
4   5   7

Level links:
1 -> nil
2 -> 3 -> nil
4 -> 5 -> 7 -> nil

Walk:
- level 0: 1.next = nil
- level 1: 2.next = 3, 3.next = nil
- level 2: 4.next = 5, 5.next = 7, 7.next = nil

Pitfalls to avoid

• Using next pointers before they are built for the current level.
• Forgetting to reset the dummy/tail each level.

Debugging lens

Prepopulate Next pointers with self-links or wrong-level pointers, then verify each exact level chain and its nil terminator. Also test gaps between parents' children.

Complexity

• Time: O(n)
• Extra space: O(n) for the queue.

Implementation notes (Go)

• The supplied reference uses a BFS queue and does not rely on initial Next pointers.
• An O(1)-auxiliary alternative can build the next level with dummy/tail links, but must first establish safe level chains and clear each final Next.

Reconstruction checkpoint

Root R has children A,B; A has only right child C and B has only left child D. Incoming Next fields include B.Next=B and D.Next=A. What exact successor chains must remain, and which edges may be used to discover nodes safely?

Return to Binary Tree BFS · Module quiz