104. Populating Next Right Pointers in Each Node

Process each level left-to-right using BFS, linking each node's next pointer to the next node in the queue at the same level.

Approach

1. BFS level by level.
2. For each node in a level, set its next pointer to the next node at the same level.
3. The last node at each level points to NULL.

Complexity

• Time: O(n)
• Space: O(n) for BFS queue

import java.util.*;

class Solution {
    public TreeNode connect(TreeNode root) {
        if (root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            TreeNode prev = null;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (prev != null) prev.next = node;
                prev = node;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return root;
    }
}