Failing to set a node to null

Question

I'm trying to construct a binary search tree but have a problem when creating my own method to remove a node.

I know how to deal with removing a node when it has two children, one child or no child, which I have taken into account in my code. But when I am really trying to delete it and set it to null, nothing happens. The node is still there, and the smallest number isn't replacing it when the node has two children. (one technique to deal with removing a node with two children). Where's the problem?

Below is the code:

public static void main(String[] args) {
    BST root=new BST(10);
    root.insert(5);
    root.insert(15);
    root.insert(2);
    root.insert(5);
    BST node=root.insert(13);
    root.insert(22);
    root.insert(1);
    root.insert(14);
    BST smallestNode=root.insert(12);
    System.out.println(node.left.value);
    System.out.println(root.contains(4));
    System.out.println(root.remove(12));
    System.out.println(root.contains(12));
}

public static class BST {
    public int value;
    public BST left;
    public BST right;

    public BST(int root) {
        this.value = root;
    }

    public BST insert(int value) {
        BST currentNode=this;
        while(true){
            if(value>= currentNode.value){
                if(currentNode.right ==null){
                    currentNode.right=new BST(value);
                    currentNode=currentNode.right;
                    break;
                }
                currentNode= currentNode.right;
            }else{
                if(currentNode.left==null){
                    currentNode.left=new BST(value);
                    currentNode=currentNode.left;
                    break;
                }
                currentNode= currentNode.left;
            }
        }
        return currentNode;
    }
    public boolean contains(int value) {
        BST currentNode=this;
        while(true){
            if(value>= currentNode.value){
                if(currentNode.right ==null){
                    return false;
                }
                currentNode= currentNode.right;
                if(currentNode.value==value){
                    return true;
                }
            }else{
                if(currentNode.left==null){
                    return false;
                }
                currentNode= currentNode.left;
                if(currentNode.value==value){
                    return true;
                }
            }
        }
    }
    public BST remove(int value) {
        BST currentNode=this;
        if(currentNode.right==null &¤tNode.left==null){
            return this;
        }
        while(true){
            if(value>= currentNode.value){
                if(currentNode.right==null){
                    return this;
                }
                currentNode= currentNode.right;
                if(currentNode.value==value){
                    if(currentNode.left!=null&¤tNode.right==null){
                        currentNode=currentNode.left;
                        return currentNode;
                    }else if(currentNode.right!=null&¤tNode.left==null){
                        currentNode=currentNode.right;
                        return currentNode;
                    }else if(currentNode.right==null&¤tNode.left==null){
                        currentNode=null;
                        return currentNode;
                    }else{
                        currentNode.value=smallestValueSearchService(this);
                        currentNode.right=this.right;
                        currentNode.left=this.left;
                        return currentNode;
                    }
                }
            }else{
                if(currentNode.left==null){
                    return this;
                }
                currentNode= currentNode.left;
                if(currentNode.value==value){
                    if(currentNode.left!=null&¤tNode.right==null){
                        currentNode=currentNode.left;
                        return currentNode;
                    }else if(currentNode.right!=null&¤tNode.left==null){
                        currentNode=currentNode.right;
                        return currentNode;
                    }else if(currentNode.right==null&¤tNode.left==null){
                        currentNode=null;
                        return currentNode;
                    }else{
                        currentNode.value=smallestValueSearchService(this);
                        currentNode.right=this.right;
                        currentNode.left=this.left;
                        return currentNode;
                    }
                }
            }
        }
    }
}
//?: conditional
public static int smallestValueSearchService(BST binaryTree){
    if(binaryTree.left==null){
        int temp=binaryTree.value;
        binaryTree=null;
        return temp;
    }else{
        return smallestValueSearchService(binaryTree.left);
    }
}

This is a visual illustration of what I am supposed to achieve and what my code produces:

Image of my output compared to expected output

This is the binary tree:

This is the binary tree

trincot · Answer

The main issue is that assigning to a variable is never going to change anything to the tree. The variable currentNode references a node, and when you set currentNode to some other node reference, or to null, you just modify what that variable has, not anything in the tree.

This misunderstanding can be seen both in remove as in smallestValueSearchService. Although the latter function name suggests it is just searchnig a value, you seem to want to remove a value. But nothing gets removed there either.

There are several other things to note about your remove method, including:

The first if will just return the current node without checking its value (it could have been the value to remove!).
There is quite a big chunk of code that is repeated. This should be avoided.
The while loop makes no sense, as in all cases a return will be executed in its first (and only) iteration.
Because the loop doesn't loop, and there is no recursion either, currentNode is never going to reference a node that is deeper in the tree than its first two levels.
remove returns a node reference, but there is no caller of remove that actually does something with that returned value. This is a crucial point, as the caller should assign it to a node. For instance, if the tree would have only one node, and it has the value to remove, then somewhere you should set root to null.
smallestValueSearchService is called with this as argument, but that is wrong. It should look for the smallest value in the right subtree of the node that has the value to be removed.

It is strange that you have defined smallestValueSearchService as a static method instead of an instance method. I would also suggest that this function will only return the smallest value and will not attempt to delete it. You can then use the remove method to actually remove it once it has been found.

Here is a correction for the remove function. I renamed the smallestValueSearchService static method into getSmallestValue, and it is now an instance method:

    public BST remove(int valueToRemove) {
        if (valueToRemove > value) {
            if (right != null) {
                right = right.remove(valueToRemove);
            }
        } else if (valueToRemove < value) {
            if (left != null) {
                left = left.remove(valueToRemove);
            }
        } else {
            if (right == null) {
                return left;
            } else if (left == null) {
                return right;
            } else {
                value = right.getSmallestValue();
                right = right.remove(value);
            }
        }
        return this;
    }
    
    public int getSmallestValue(){
        if (left == null) {
            return value; 
        } else {
            return left.getSmallestValue();
        }
    }

The main program should not print the result from the remove call, but assign it to the root variable:

        root = root.remove(12);

Failing to set a node to null

1 Answers