Summing binary tree levels

Question

I'm trying to traverse a binary tree by level, then sum the ints held in each node per level which is held in levelSum. I then want to multiply the levelSum by the number of the level that I am at and add this to the totalSum. When I run it I get a NullPointException on line 15 but I haven't been able to figure out why.

public int depthSum() {
    Queue<IntTreeNode> q = new LinkedList<IntTreeNode>();
    int totalSum = 0;
    int levelSum = 0;
    int multiplier = 1;
    int nodesPerLevel = 0;
    if(overallRoot != null) {
        q.offer(overallRoot);
        nodesPerLevel += 1;
        while(!q.isEmpty()) {
            int countDown = nodesPerLevel;
            while(countDown > 0) {
                countDown--;
                IntTreeNode n = q.remove();
                levelSum += n.data; //this is line 15
                if(n.left != null) {
                    q.offer(n.left);
                    nodesPerLevel++;
                }
                if(n.right != null) {
                    q.offer(n.right);
                    nodesPerLevel++;
                }
            }
            totalSum += (multiplier * levelSum);
            levelSum = 0;
            multiplier++;
        }
    }
    return totalSum
}

This is the stack trace:

NullPointerException on line 15:
java.lang.NullPointerException
at IntTree.depthSum (Line 15)

possible duplicate of [What is a Null Pointer Exception, and how do I fix it?](http://stackoverflow.com/questions/218384/what-is-a-null-pointer-exception-and-how-do-i-fix-it) — Oleg Estekhin, Jun 18 '14 at 06:32
Well, if `tempSum += n.data` throws an NPE, then obviously `n` is `null`, which means that `q.remove()` returned `null`, which means that the queue was empty. OH ... just saw: If `tempSum` is of type `Integer` and was not initialized, this could also be `null`. Is it declared as an instance field? If yes, remove it and use a local variable instead. — Seelenvirtuose, Jun 18 '14 at 06:35
tempSum should have been levelSum. This didn't fix the problem though. I check that the root is not null in the first conditional statement, then put it into the queue. When I make the new IntTreeNode n and assign it to the node in the queue it shouldn't be null right? — Joshua Oliphant, Jun 18 '14 at 06:49

bcorso · Accepted Answer · 2014-06-18T07:34:21.083

If I had to guess, probably countdown does not hold the correct value; however, given that a lot of the variables are undefined in the code it is hard to tell exactly where the failure is.

If countdown is faulty, the inner loop will eventually empty the queue. When this happens you will get n = null, and trying to call n.data, n.left, or n.right will give a NullPointerException.

Below is a similar version of what I think you are trying to do (Ideone example here):

public int depthSum(IntTreeNode root) {
    if(root == null) throw new NullPointerException();

    Queue<IntTreeNode> q = new LinkedList<IntTreeNode>();
    q.add(root);
    int siblings = 1;
    int totalSum = 0, levelSum = 0, level = 0;

    while(!q.isEmpty()) {
        IntTreeNode n = q.remove();            // Only remove one node per loop
        levelSum += n.data;

        if(n.left != null)                     // Add left child 
            q.add(n.left);

        if(n.right != null)                    // Add right child
            q.add(n.right);

        if(--siblings == 0){                   // All siblings have been probed
            siblings = q.size();               // All remaining Nodes are siblings
            totalSum += levelSum * level;      // increment totalSum
            level++;                           // increment level
            levelSum = 0;                      // reinitialize levelSum
        }
    }
    return totalSum;
}

score -1 · Answer 2 · answered Jun 18 '14 at 06:56

-1

The main point for NullPointException should be nodesPerLevel not reset to 0; countDown should be larger than the queue size and causes q.remove throw NullPointException.

nodesPerLevel should reset to 0 just after countDown = nodesPerLevel.

this code snippet looks unable to compile, e.g. tempSum looks to be levelSum. so the finally result sill need verification.

answered Jun 18 '14 at 06:56

Don Xu

29
1

`nodesPerLevel` could never give `NPE` in this code because its type is primitive type. – Andremoniy Jun 19 '14 at 07:07
@Andremoniy, thanks for your comments, I am glad my answer got response. you're right that **nodePerLevel** not give **NPE**. but since **nodesPerLevel** not reset to **0**, it will be greater than the size of of **q** and cause **q.remove** throw **NPE**. – Don Xu Jun 20 '14 at 10:41

Summing binary tree levels

2 Answers2