How to "delete" a node from a binary search tree in Java?

Question

I made a binary search tree in Java but I'm having troubles whit the deleting nodes part. I managed to erase the node when it has only 1 son, and I have the idea to make the deletion when it has 2 sons, anyways the method I'm using when it has no sons (when it's a leaf) is not working in Java. Normally in C++ I would assign the Node "null" but it doesn't work here.

if (numberOfSons(node) == 0) {
            node= null;
            return true;
}

That's the portion of the code that takes care of the nulling part. When I debug it, it is referencing the correct node and it's assigning it the null value, but when I return to the Frame where I'm calling the delete method for my tree the node is still there. What's the correct way to "null" an object in Java? I thought everything was a pointer in here and therefore this would work, but I think it doesn't.

Answer 1

When you're nulling something you just make the reference in the scope you're in null. It doesn't affect anything outside.

Let me explain by example. Say you have a method foo:

public void foo(Node node) {
    node = null;
    if(node == null) {
      System.out.println("node is null");
    } else {
      System.out.println("node is not null");
    }
}

Now you call it like this:

public void doSomething() {
   Node node = new Node();
   foo(node);
    if(node == null) {
      System.out.println("Original node is null");
    } else {
      System.out.println("Original node is not null");
    }   
}

In your console you'll get:

node is null
original node in not null

The reason is that it's not a pointer, it's a reference. When you're nulling a reference, you just say "make this reference synonym to null". It doesn't mean that the object is deleted, it may still exist in other places. There is no way to delete objects in java. All you can do is make sure no other object points to them, and the garbage collector will delete the objects (sometime).

Answer 2

Nothing remains but to reinsert either left or right subtree. For instance:

class BinaryTree<T extends Comparable<T>> {
    class Node {
        Node left;
        Node right;
        T value;
    }

    Node root;

    void delete(T soughtValue) {
        root = deleteRec(root, soughtValue);
    }

    Node deleteRec(Node node, T soughtValue) {
        if (node == null) {
            return null;
        }
        int comparison = soughtValue.compareTo(node.value);
        if (comparison < 0) {
            node.left = deleteRec(node.left, soughtValue);
        } else if (comparison > 0) {
            node.right = deleteRec(node.right, soughtValue);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                // Two subtrees remain, do for instance:
                // Return left, with its greatest element getting
                // the right subtree.
                Node leftsRightmost = node.left;
                while (leftsRightmost.right != null) {
                    leftsRightmost = leftsRightmost.right;
                }
                leftsRightmost.right = node.right;
                return node.left;
            }
        }
        return node;
    }
}

As Java does not have aliases parameters as in C++ Node*& - a kind of in-out parameter, I use the result of deleteRec here. In java any function argument that is an object variable will never change the variable with another object instance. That was one of the language design decisions like single inheritance.