Deleting a node in a Binary Search Tree using Java

Question

Could you tell me why this code wont delete a node in a BST? Is there any logical error in my code?

    // To delete a node from the BST
public Node deleteNode(Node myRoot, int toDel) {
    if (myRoot == null) return null;
    else if (toDel < myRoot.data) myRoot.left = deleteNode(myRoot.left, toDel);
    else if (toDel > myRoot.data) myRoot.right = deleteNode(myRoot.right, toDel);
    else {
        // Leaf node
        if (myRoot.right == null && myRoot.left == null) {
            myRoot = null;
        } else if (myRoot.left == null) { // No left child
            myRoot = myRoot.right;
        } else if (myRoot.right==null){ // No right child
            myRoot = myRoot.left;
        }
    }
    return myRoot;
}

NOTE :- This code only deletes the nodes with one child or no child. I am currently working on deleting a node with 2 children so please dont solve that for me.

Seems like the problem is when you try to delete the node by reassigning myRoot, you're just reassigning the value of the parameter variable which doesn't actually affect the tree itself since Java is pass-by-value. — Flaom
Alright I understood that fact just now. How do you reckon I solve this?? — spiritmonster
To delete a node, you'll need to make it so that no references are being held for that object, so I think what you'd want to do is rather than check if the current node needs to be deleted, you would inspect its children to see if one of them should be deleted. Example: myRoot.left points to a node that needs to be deleted. If myRoot.left is a leaf node, setting myRoot.left = null would be sufficient. If it's not a leaf node, you will need to assign it to another node — Flaom
Ok i get it a bit. Could you edit my code and give a final answer so i could get a better understanding. Thank You. — spiritmonster

John D John D · Accepted Answer · 2021-01-18T04:37:17

If 0 children, simply delete node (return null for it).

If there is 1 child, simply replace the node with the child that is not null.

public Node deleteNode(Node myRoot, int toDel) {
    if (myRoot == null) {
      return null;
    } else if (myRoot.data == toDel) {
      if (myRoot.left != null) {
          return myRoot.left;
      } else if (myRoot.right != null) {
          return myRoot.right;
      } else {
          return null;
      }
    }
    ...
   return myRoot;
}

Deleting a node in a Binary Search Tree using Java

1 Answers