How to find sum of node's value for given depth IF the tree is NOT complete?

Question

I've asked very similar question before and should have mentioned more detailed. Last time was "how to find sum of node's value for given depth in binary tree" in PHP.

sum(Node, Level) = 
  if (Level == 0) return Node.value;
  else return f(Node.left, Level-1) + 
              f(Node.right, Level-1).

So now I tried to write this in Java. And Java throws nullPointerException. The reason is because the code below does not handle in case the tree is not complete.

    public int getNodeValueByDepth(Node n, int level) {

            if(level == 0) {
                return n.data;
            }
            else {
                return getNodeValueByDepth(n.left, level-1) + 
                       getNodeValueByDepth(n.right, level-1);
            }
    }

My test tree structure is:

/*
         * construct tree
         *                                    sum of node's value   
         *              5          depth 0 ==> 5
         *             / \               
         *           3    10       depth 1 ==> 13
         *          / \   / \
         *         2  4   6  11    depth 2 ==> 23
         *               / \
         *              7   9      depth 3 ==> 16
         *            
         *                         depth 4 ==> null
         *           
         */

So when I call getNodeValueByDepth(root, 3) which is 7+9, it throws and null pointer exception error. I tried to add logic to handle the case where node left and right is null but still can't figure out how and I can't sleep without solving this..

Could anyone give me a hint? I tried but not it just returns 0.

public int getNodeValueByDepth(Node n, int level) {

        int sum = 0;

        if(level == 0) {
            return sum + n.data;
        }
        else if(n.left != null) {
            return sum += getNodeValueByDepth(n.left, level-1);
        }
        else if(n.right != null) {
            return sum += getNodeValueByDepth(n.right, level-1);
        }
        else {
            return sum + 0;
        }

    }

Answer 1

Your control statements use else in every case, so only one ever gets evaluated. Thus if it evaluates for the left side, when it returns it doesn't do the right side.

public int getNodeValueByDepth(Node n, int level) {
    int sum = 0;

    /** If we have reached our desired level */
    if (level == 0) {
        if (n != null) {
            /** Assuming data is an int and not nullable */
            return n.data;
        } else {
            /** Change this to 0 if you don't want an error condition */
            return -1;
    }

    /** We are not the desired level, so get the sum of .left and .right, knowing either may not exist */
    if (n.left != null) {
        sum += getNodeValueByDepth(n.left, level-1);
    }

    if (n.right != null) {
        sum += getNodeValueByDepth(n.right, level-1);
    }

    /** Now have evaluated every possible child and stored the sum, even if it is 0 */
    return sum;
}

Note: Check for syntax errors, I wrote this on a machine without Java.

Answer 2

In the last example, take out the last "Else", have it return the sum regardless of the success of the previous conditions and it should work.