Delete method for Binary Search Trees?

Question

Ok, so I wanted to write a delete method that works for any "delete-case" for Binary Search Trees and this is my attempt:

 public void delete(int key) {
 if (root.value == key) {
   root = root.right;
   root.left = root.right.left;
   return;
 }
 else {
   deleteRecursive(key, root);  ***LINE 58***
 }

 }

 public void  deleteRecursive(int key, BinaryNode node) {
 if (node == null) {
   System.out.println("ERROR");
   return;
 }
 else {
   if (key < node.value) {
     // continue search on left
     if (node.left.value == key) {
       if (node.left.left == null && node.left.right == null) {
         node.left = null;     
       }
       else if (node.left.left == null){
         node.left = node.left.right;
       }
       else if (node.left.right == null){
         node.left = node.left.left;
       }
       else{
         node.left = node.left.right;
         node.left.left = node.left.right.left;  ***LINE 83***
       }
     }
     else {
       deleteRecursive (key, node.left);
     }
   }
   else if (key > node.value){
     // continue search on right
     if (node.right.value == key) {
       if (node.right.left == null && node.right.right == null) {
         node.right = null;
       }
       else if (node.right.left == null){
         node.right = node.right.right;
       }
       else if (node.right.right == null){
       }
       else if (node.left.left != null && node.left.right != null){
         node.right = node.right.right;
         node.right.left = node.right.right.left;
       }
     }
     else {
       deleteRecursive (key, node.right);
     }
   }
 }
}

But when I actually use the delete method in Main its gives out a NullPointerException.

The error-message reads :

Exception in thread "main" java.lang.NullPointerException
        at BinaryTree.deleteRecursive(BinaryTree.java:83)
        at BinaryTree.delete(BinaryTree.java:58)
        at Main.main(Main.java:14)

So I assume that it is in line 83 and 58 (marked in code).

I've been sitting here for the last hour trying to figure it out and can't seem to get it.

I'm not the best in Java so I thought i could look for some help here! :)

Here are all the files to run the program (everything except for the delete method was already given) : https://www.dropbox.com/sh/r1bt2880hnn6tjm/AADsRsOOzuiNKHp-ZC-IrvVta?dl=0

Answer 1

Since you are trying to remove from Binary Search Tree, better make it totally recursive rather than partially.

private BinaryNode deleteRecursive( int data,BinaryNode node) {
  if(node==null){
      return null;
  }
  if(data==node.value)
  {
      if(node.left!=null && node.right!=null){
          BinaryNode minNode = getHighestNodeFromRight(node.right);
          node.value = minNode.value;
          node.right = deleteRecursive(minNode.value, node.right);

          //System.out.println(minNode);
      }
      else if(node.left==null){
      return node.right;
      }
      else{
      return node.left;
      }
  }
  else if(data>node.value){
  node.right = deleteRecursive( data,node.right);
  }
  else{
      node.left = deleteRecursive(data, node.left);
  }
  return node;
}


public BinaryNode getHighestNodeFromRight(BinaryNode node){
      if(node.left==null){
          return node;
      }
      else{
          BinaryNode n = getHighestNodeFromRight(node.left);
          return n;
      }
}