Determine size of Integer Binary Tree via recursion

Question

I have the classes BinaryTreeNode(int value) with its left and right child and BinaryTree(int rootVal) with BinaryTreeNode root with rootVal as its value. I developed a code to calculate the number of nodes in the tree (in class BinaryTreeNode), but it doesn't work because of a NullPointerException:

public int size(){
    if(this == null) {    // base case
        return 0;
    } else {
        return 1 + left.size() + right.size();
    }
}

However another solution I found, with a similar strategy, works:

public int size(BinaryTreeNode refNode){
    if(refNode == null) {    // base case
        return 0;       
    } else {
        return 1 + size(refNode.left) + size(refNode.right); 
    }
}

I have understood why my code throws an exception (it is because left/right would point to null). But I would like to understand why the second solution works with quasi the same principle. Thank you in advance!

Answer 1

In your first example you try to find the size before you check for null:

first you call

left.size()

and then inside the size() method you check to see if the object you just called the method on is null

if(this == null) {    // base case
    return 0;
...

so if left is null, you get the NPE before you get into the size() method.

The main thing to remember here, is that this can never be null. If it was, you couldn't be running a method on it in the first place. So you weren't actually terminating your recursion on a null case like you thought you were.

In the second you check for null first:

if refNode.left is null here

    return 1 + size(refNode.left) + size(refNode.right); 

the size() method does a pre-check

if(refNode == null) {    // base case
    return 0;
...

and safely returns 0.

You could make your first method work by explicitly putting the null-check first on each branch:

public int size(){
    return 1 
        + left == null ? 0 : left.size()    // check for null first
        + right == null ? 0 : right.size(); // check for null first
}

Answer 2

The base case is organized in the wrong way; checking for null on the current instance makes no sense. The method should be rewritten as follows.

public int size(){
    int sizeLeft = 0;
    if (this.left != null)
        sizeLeft = left.size();
    int sizeRight = 0;
    if (this.right != null)
        sizeRight = right.size();
    return 1 + sizeLeft + sizeRight;
}