Search code examples
javatreebreadth-first-search

Weird bug when solving LeetCode 117

I'm trying to solve LeetCode problem 117. Populating Next Right Pointers in Each Node II:

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1

enter image description here

I implemented a simple BFS, but it fails the first test case. What's pretty weird is that, according to my output, at the end of the third iteration of the while loop the queue size is 0, but when it checks the queue for the forth iteration's condition, it magically changed to 1!!!

I'm so confused by this behavior.

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            System.out.println("-");
            System.out.printf("size: %d%n",  queue.size());
            for(int i=0; i<size-1; i++){
                Node curr = queue.poll();
                System.out.println("poll");
                curr.next = queue.peek();
                if(curr.left != null){
                    System.out.println(curr.left.val);
                    queue.offer(curr.left);
                } 
                if(curr.right != null){
                    System.out.println(curr.right.val);
                    queue.offer(curr.right);
                } 
            }
            Node last = queue.poll();System.out.println("poll");
            // System.out.println(last.val);
            last.next = null;
            System.out.printf("size: %d%n",  queue.size());
            if(last.left != null){
                System.out.println(last.left.val);
                queue.offer(last.left);
            } 
            System.out.printf("size: %d%n",  queue.size());
            if(last.right != null){
                System.out.println(last.right.val);
                queue.offer(last.right);
            } 
            System.out.printf("size: %d%n",  queue.size());
        }
        return root;
    }
}

Output generated:

-
size: 1
poll
size: 0
2
size: 1
3
size: 2
-
size: 2
poll
4
5
poll
size: 2
size: 2
7
size: 3
-
size: 3
poll
poll
poll
size: 0
size: 0
size: 0
-
size: 1
poll
Solution

  • but when it checks the queue for the forth iteration's condition, it magically changed to 1!!!

    The output of LeetCode is misleading you into thinking that output belongs to the same test case. It is not. That 1 comes from running a second test case.

    And it is with that test case that your code has an issue. The test provides an empty tree to your function, i.e. root is null. Your code will put that null on the queue (and you output the 1), but then when this "node" is pulled from the queue, the reference to its next property triggers an exception.

    The fix is of course simple...

    Add a null check at the top of your function.