javanullpointerexceptionavl-tree

Trouble updating height and BF for an AVL tree


So I'm trying to update the height and balance factor (BF) for an AVL tree. I'm doing this by using the updateHeightAndBF() method. However, my program keeps getting an error saying:

This updateHeightAndBF test was inconclusive due to: java.lang.NullPointerException

Here is the code for the method:

public void updateHeightAndBF(AVLNode<T> currentNode) {
        
        //Store the left child height in a variable (keep in mind the height of a null node; you'll have to account for this!)
        AVLNode<T> leftChild = currentNode.getLeft();
        if (leftChild == null) {
           leftChild.setHeight(-1);
        }
        
        //Store the right child height in a variable (keep in mind the height of a null node; you'll have to account for this!)
        AVLNode<T> rightChild = currentNode.getRight();
        if (rightChild == null) {
           rightChild.setHeight(-1);
        }
        
        //Set the height of the node to be: max(left child's height, right child's height) + 1
        currentNode.setHeight(Math.max(leftChild.getHeight(), rightChild.getHeight()) + 1);
        
        //Set the balance factor of the node to be: left child's height - right child's height
        currentNode.setBalanceFactor(leftChild.getHeight() - rightChild.getHeight());
}

I think the problem is that I'm trying to assign a height to a null node? But I'm supposed to give it a height of -1 if there is no node child (aka null node). So how do I assign a height of -1 to a null node if the program won't let me?

I'm not sure what else to try.


Solution

  • So how do I assign a height of -1 to a null node if the program won't let me?

    It makes no sense to try to assign something to nothing. null represents the absence of a node. Instead you can assign that -1 to a local variable, and use it in the calculation of the height of the current node.

    Here is a correction of your function

    public int updateHeightAndBF(AVLNode<T> currentNode) {
        AVLNode<T> leftChild = currentNode.getLeft();
        AVLNode<T> rightChild = currentNode.getRight();
        // Calculate the heights of the child nodes
        int leftHeight = leftChild == null ? -1 : leftChild.getHeight();
        int rightHeight = rightChild == null ? -1 : rightChild.getHeight();
        // Use that information to derive the current node's height and balance factor
        currentNode.setHeight(Math.max(leftHeight, rightHeight) + 1);
        currentNode.setBalanceFactor(leftHeight - rightHeight);
    }