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.

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)

Do a level-order traversal. For each level, wire nodes in the order you pop them.

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.
   • Set the last node's Next to nil (or leave as nil).
   • Enqueue children of each popped node as you go.
4. Return root.

Correctness sketch

• Invariant: nodes popped in the same BFS layer are in left-to-right order, so you can chain Next pointers linearly.
• The queue holds exactly the current level’s nodes before each level pass.
• Processing size nodes and enqueueing children builds the next level correctly.
• Collected level results therefore match the required traversal.

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.

Complexity

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

Implementation notes (Go)

• Use a dummy head and tail to build the next level in O(1) extra space.
• Reset dummy/tail each level; advance using existing Next pointers.