Leetcode BFS question: why does my queue have a null in it?

Question

I am doing a leetcode BFS question: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/

my solution is as below, it passes:

class Solution {
    public Node connect(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
      
        while(!q.isEmpty())
        {
            Queue<Node> childQ = new LinkedList<>();
            while(!q.isEmpty())
            {
                Node curr=q.remove();
                if(curr==null) break;
                curr.next=q.peek();
                if(curr.left!=null)
                {childQ.add(curr.left);childQ.add(curr.right);}
            }
            q=childQ;
        }
        return root;
    }
}

It passes only after I added the null check for the last-ever node in the queue.

if(curr==null) break;

But why would the curr be null? Somewhere a null is passed into the childQ in the last iteration. But I can't spot where. Can someone lend me an eye?

Thanks!

Answer 1

The null is not coming from the childQ queue. It can only happen when root is null since the code challenge description says that the number of nodes in the tree could be 0. This means root is null.

So you can remove that if statement, but you should have one at the very start of the function to detect this corner case:

    public Node connect(Node root) {
        if(root==null) return root; // corner case
        Queue<Node> q = new LinkedList<>();
        q.add(root);
      
        while(!q.isEmpty())
        {
            Queue<Node> childQ = new LinkedList<>();
            while(!q.isEmpty())
            {
                Node curr=q.remove();
                curr.next=q.peek();
                if(curr.left!=null)
                {
                    childQ.add(curr.left);
                    childQ.add(curr.right);
                }
            }
            q=childQ;
        }
        return root;
    }