Binary Search Tree, working with Deleting a Node

[bizak]

Hello!

I've been staring at my code for a while and I really have no idea where I'm going wrong. I'm working on deleting a specific node (for example, the integer 317)....but for some reason I just keep getting a nullpointer expression. I get the error when it goes into if ((hp.getLp() != null) && (hp.getRp() != null)). I've tried numerous things, but I've gotten to the point where I can't tell where it is messing up exactly. Would someone be able to point me in the right direction? Thank you so much!

public void Delete1(int val)
{
    root = Delete2(root, val);
}

public Node Delete2(Node hp, int val)
{
    //Empty case
    if (hp == null)
    {
        System.out.println("The following data was not found: " + val);
        return hp;
    }

    //Need to go down right tree
    if (val < hp.getData())
    {
        //search further
        hp.setLp(Delete2(hp.getLp(), val));
        return hp;
    }

    //Need to go down left tree
    else if (val > hp.getData())
    {
        //search further
        hp.setRp(Delete2(hp.getRp(), val));
        return hp;
    }

    else
    //(dx == hp.getData() found the node
    {
        //Node has been found
        //else must be dx == hp.getData()
        System.out.println("Deleting: " + val);

        if ((hp.getLp() == null) && (hp.getRp() == null))
        {
            return null;
        }

        if ((hp.getLp() == null) && (hp.getRp() != null))
        {
            return hp.getRp();
        }

        if ((hp.getLp() != null) && (hp.getRp() == null))
        {
            return hp.getLp();
        }

        if ((hp.getLp() != null) && (hp.getRp() != null))
        {
            //find the maximum
            Node max = FindMax1(hp.getLp());

            //Bring max data to hp
            hp.setData(max.getData());
            hp.setLp(Delete2(hp.getLp(), max.getData()));
            return hp;
        }

        return hp;
    }
}


public Node FindMax1(Node hp)
{
    int result = Integer.MAX_VALUE;
    if(hp.getLp() != null)
    {
        result = hp.getData();
        System.out.println(result);
    }
    else
    {
        return null;
    }
    return null;
}

[JamesCherrill]

Can you confirm the exact message and the line it refers to? The line you quoted (38) will only throw an NPE if hp is null, but to get there it must have executed line 24, so hp cannot be null (or I'm mis-reading your code, in which case, apologies)

[bizak]

The initial error is at this line;

hp.setRp(Delete2(hp.getRp(), val));

It also says that it is at this line as well;

hp.setData(max.getData());

I would still like to use this method, but I was looking around last night and trying different things and came up with something else for the last if in the delete method;

if ((hp.getLp() != null) && (hp.getRp() != null))
            {        
                Node temp = hp.getLp();
                Node previous = hp;
                while(temp.getRp() != null)
                {
                    previous = temp;
                    System.out.println("HI");
                    temp = temp.getRp();
                }
                hp = temp;
                if(previous.getLp() == hp)
                {
                    previous = temp.getLp();
                }
                else if (previous.getRp() == hp)
                {
                    previous = temp.getRp();
                }

[bizak]

I submitted before I had a chance to explain that last portion. I tried a new method, which no deletes the numbers I want, however, it also deletes every number after it. I'm not sure which I should go to, nor which is most effective.

[bizak]

My apologies, I forgot to include the message that it sent for the initial snippet of code;

Exception in thread "main" java.lang.NullPointerException

[JamesCherrill]

To debug a NPE insert print statements that print every value (variable or expression or method call that returns a value) used on the line where the exception was thrown. THis tells you which variable or expression was null. Then trace back thru your logic to find out why.