i am not getting the results i am expecting in binary search tree.

[john steward]

i don't see any nodes that i add.not sure why getting this error.
duplicate found
Exception in thread "main" java.lang.NullPointerException
at binarysearchtree.delete(binarysearchtree.java:111)
at binarysearchtree.main(binarysearchtree.java:196)
Java Result: 1

public class node<T>
{
     public node<T>  root ;
    public T data;
    public node left;
    public node right;


    public node (T newData)
    {
        data = newData;
        left = null;
        right = null;
        root=null;  
    }

    public node ()
    {
        data = null;
        left = null;
        right = null;
    }

    

   

   

    public void setData (T newData)
    {
        data = newData;
    }

    public T getData ()
    {
        return data;
    }

    public void setLeft (node newLeft)
    {
        left = newLeft;
    }

    public node getLeft ()
    {
        return left;
    }

    public void setRight (node newRight)
    {
        right = newRight;
    }

    public node getRight ()
    {
        return right;
    }
    public node getRoot ()
    {
        return root;
    }

    public void setRoot (node newRoot)
    {
        root = newRoot;
    }
   
   

    public boolean equals (node theOther)
    {
        return this.data.equals (theOther.data);
    }

  public int compareTo (node theOther)
    {
        return ((Integer) (this.getData ())).compareTo ((Integer) (theOther.getData ()));
    }

  



}

public class binarysearchtree<T>  extends node<T>
{
    public node root;
    public binarysearchtree ()
    {
        root=null;
    }


    public boolean empty ()
    {
        return(root==null);
    }

   public boolean addOne (T newMember)
    {
        boolean success = true;
        node<T> newNode = new node<T> (newMember);
        if (empty ())
            setRoot (newNode);
        else
        {
            node p = null;
            node c = getRoot ();
            int compare = 0;

            while (c != null)
            {
                compare = newNode.compareTo (c);
                if (compare == 0)
                {
                    System.out.println ("duplicate found");
                    success = false;
                    return success;
                }
                else
                {
                    p = c;
                    if (compare > 0)
                        c = c.getRight ();
                    else
                        c = c.getLeft ();
                }
            }

            if (compare > 0)
                p.setRight (newNode);
            else
                p.setLeft (newNode);
        }
        return success;

    }

   public T delete (node key)
    {
       T dataInDeleted = null;
       if (!empty ())
       {
           node p = null;
           node c = getRoot ();
           int compare = 0;

            while (c != null)
            {
                compare = key.compareTo (c);
                if (compare == 0)
                    break;
                else
                {
                    p = c;
                    if (compare > 0)
                        c = c.getRight ();
                    else
                        c = c.getLeft ();
                }
            }

           if (c == null)
           {
               System.out.println  ("not found");
               return dataInDeleted;
           }
           else
           {
               dataInDeleted = (T) c.getData ();
               node betweenPnC  = null;

               // covers left and one-child cases
               if (c == getRoot ()) //
                   betweenPnC = getRoot ();
               else if (c == p.getLeft ())// if it is left child
                   betweenPnC = p.getLeft ();
               else
                   betweenPnC = p.getRight ();

               if (betweenPnC.getRight () == null)
                   betweenPnC = betweenPnC.getLeft ();
               else if (betweenPnC.getLeft () == null)
                   betweenPnC = betweenPnC.getRight ();
               //end of leaf and one-child cases

               //2-child case, go right once then keep going left till null
               node px = c;
               node pc = c.getRight ();
               while (pc.getLeft () != null)
               {
                   px = pc;
                   pc = pc.getLeft ();
               }

               c.setData ((T) pc.getData ());

               if (px == c)
                   px.setRight (pc.getRight ());
               else
                   px.setLeft (pc.getRight ());
           }

      }

     return dataInDeleted;



   }
   public void inOrder (node root)
    {
        if (root != null)
        {
            inOrder (root.getLeft ());
            System.out.println (root);
            inOrder (root.getRight ());
        }
    }

   //use inorder traversal
   public void traverse ()
    {
        node startPoint = getRoot ();
        inOrder (startPoint);


    }
public void setRoot (node newRoot)
    {
        root = newRoot;
    }
    public node getRoot ()
    {
        return root;
    }
    public node binarySearch (node key)
    {
		node found = null;
		node temp = getRoot ( );
		while (temp != null)
		{
				int x = key.compareTo (temp);
				if (x == 0)
				{
					found = temp;
					break;
				}
				else if (x < 0)
					temp = temp.getLeft ( );
				else
					temp = temp.getRight ( );
		}

		return found;
	}









 public static  void main(String[] args) {

binarysearchtree<Integer> tree  = new binarysearchtree<Integer>();
		
            
tree.addOne(88);
tree.addOne(88);


tree.delete(new node(88));
tree.delete(new node(7));
tree.addOne(2);
tree.traverse();



              
		

		System.out.println(tree);





 }

   
}

[Knute Snortum]

Welcome to the ranch.

There is no guarantee that the left node won't be null, so when you do pc = pc.getLeft(), pc may be null. Then when you do c = pc.getData() you get the NullPointerException.

Also, don't override equals() without overriding getHash() too.

[Paweł Baczyński]

Knute Snortum wrote:Also, don't override equals() without overriding getHash() too.

You probably meant hashCode()

[Knute Snortum]

Yes, indeed! getHash() is something else altogether!

[Campbell Ritchie]

A binary tree is guaranteed to have nulls in; I think you always have one more null than there are “real” values in it. So an inOrderTraversal method might look like this

//...
if (left != null)
{
   left.inOrderTraversal();
}
System.out.println(this.value);
if (right != null)
{
   right.onOrderTraversal();
}
//...

I do not usually like things like if (xyz != null) … but in this instance it is unavoidable and must be used.