Question

I have code for an AVL tree. I Have have a node class and tree class. I need a  node object that refrences the root(top) of the tree. my current code throws NullPointerException when I try to access the root properties. here is the important snippets of my code, it is in java.

public class Node {
    private Node left=null,right=null;
    public int height=1;
    private String Item;
    private int balance=0; 
    Node(String item) { 
    this.Item=item; }
}
--------------------------------------------------

public class AVLTree {
    public Node root;
    public AVLTree(){
     root=null;
 }

public void insert(String str){
    AVLTree t = new AVLTree();
    root.setItem(str);
    root=t.insert(root,str);
}
public void delete(String str){
    AVLTree t = new AVLTree();
    root.setItem(str);
    t.deleteNode(root,str);
}

private Node insert(Node node, String str) {
    deleteNode(node, str);   
    if (node == null) {
        return(new Node(str));
    }
    if (str.compareTo(node.getItem()) <1)
        node.setLeft(insert(node.getLeft(),str));
    else
        node.setRight(insert(node.getRight(),str));
    node.height = Math.max(height(node.getLeft()), height(node.getRight())) + 1;
    int balance = getBalanceNode(node);
    if (balance > 1 && str.compareTo(node.getLeft().getItem())<1)
        return rightRotate(node);
    if (balance < -1 && str.compareTo(node.getRight().getItem())>1)
        return leftRotate(node);
    if (balance > 1 && str.compareTo(node.getLeft().getItem())>1)
    {
        node.setLeft(leftRotate(node.getLeft()));
        return rightRotate(node);
    }
    if (balance < -1 &&str.compareTo(node.getRight().getItem())<1)
    {
        node.setRight(rightRotate(node.getRight()));
        return leftRotate(node);
    }
    return node;
}

private Node deleteNode(Node node, String str) {
    if (node == null)
        return node;
    if (str.compareTo(node.getItem())<1)
        node.setLeft(deleteNode(node.getLeft(),str));
    else if( str.compareTo(node.getItem())>1)
        node.setRight(deleteNode(node.getRight(),str));
    else {
        if( (node.getLeft() == null) || (node.getRight() == null) ) {
            Node temp;
            if (node.getLeft() != null)
                temp = node.getLeft();
            else
                temp = node.getRight();
            if(temp == null) {
                temp = node;
                node = null;
            }
            else
                node = temp;
            temp = null;
        }
        else {
            Node temp = minValueNode(node.getRight());
            node.setItem(temp.getItem());
            node.setRight(deleteNode(node.getRight(),temp.getItem()));
        }
    }
    if (node == null)
        return node;
    node.height = Math.max(height(node.getLeft()), height(node.getRight())) + 1;
    int balance = getBalanceNode(node);
    if (balance > 1 && getBalanceNode(node.getLeft()) >= 0)
        return rightRotate(node);
    if (balance > 1 && getBalanceNode(node.getLeft()) < 0) {
        node.setLeft(leftRotate(node.getLeft()));
        return rightRotate(node);
    }
    // Right Right Case
    if (balance < -1 && getBalanceNode(node.getRight()) <= 0)
        return leftRotate(node);
    // Right Left Case
    if (balance < -1 && getBalanceNode(node.getRight()) > 0) {
        node.setRight(rightRotate(node.getRight()));
        return leftRotate(node);
    }
    return node;
}}

Answer 1

There are 3 points in your code which i think would result in the problem:-

1.) The following code:-

        Node(String item) { 
        this.Item=item; }

Could also lead to NullPointerException as

In your case, you are not creating the object item, but rather assuming that it was created before the Node() method was called.

Alternatively, there may be cases where the purpose of the method is not solely to operate on the passed in object, and therefore a null parameter may be acceptable. In this case, you would need to check for a null parameter and behave differently. For example, Node() could be written as:

        Node(String item) { 
          If(item!=null)
          {
            this.Item=item;
          }
          else{
            return item;
          } 
        }

NullPointerExceptions are exceptions that occur when you try to use a reference that points to no location in memory (null) as though it were referencing an object. Calling a method on a null reference or trying to access a field of a null reference will trigger a NullPointerException.

2.) Your code throws NullPointerException when you try to access root as there is no null check for root in your code. It should be:-

        if (root == null)
        return root;

As it is possible that root can be null. And than you are trying to access root properties of an object with reference to null which results in NullPointerExceptions.

3.) Same is with your left and right in Node class. Here you are declaring them to null and then you are trying to access their properties as:-

        node.getLeft()

This would result in NullPointerException as they are set to null and then you are trying to access their properties.