CODEWITHSUNDEEP
javarecursionbinary-tree
soupwaylee
soupwaylee

Reputation: 127

Determine size of Integer Binary Tree via recursion

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!

Upvotes: 9

Views: 914

Answers (3)

azurefrog
azurefrog

Reputation: 10945

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
}

Upvotes: 3

Rossiar
Rossiar

Reputation: 2564

this can never be null inside the running class. You'll be getting a NPE because a Node with left == null or right == null will not be able to call the size() code, because the pointer refers to nothing.

Perhaps your code should be more defensive and check if the children are null before attempting to retrieve their size:

public int size() {
    int total = 1;
    if (left != null)
        total += left.size();
    if (right != null)
        total += right.size();
    return total;
}

Upvotes: 0

Codor
Codor

Reputation: 17605

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;
}

Upvotes: 3

Related Questions