What is wrong with my remove-method for a BST?

Question

I am working with Binary Search Trees and I am writing pseudocode for a function removeLessThan that takes node and value as input. The function is supposed to remove all the nodes that have a value less than value.

So this call:

root = removeLessThan(root, value);

...is supposed to remove all nodes with a value less than `value from the BST.

This is my attempt at writing the method in pseudocode:

removeLessThan(node, value)

    if (node == null)
        return null
    
    if (node.value >= value)
        node.left = removeLessThan(node.left, value)
    
    else if (node.value < value)
        node.left = removeLessThan(node.left, value)
        node.right = removeLessThan(node.right, value)
        node = null
    
    return node

I thought it would be a good idea to start deleting nodes with a value less than value from the bottom and then continue up recursively.

I tried visualizing what would happen with the following BST:

So, if the value is 30, we traverse left all the way down to 5 and delete this node, then we continue upwards.

However, ChatGPT tells me my code is wrong. I don’t understand the explanation, and it also says things that are incorrect.

Could somebody explain to me why my method is wrong, and what would be a better idea?

Answer 1

The mistake is in the case where node.value < value. There you always return null, but there could still be values in that node's right subtree that need to stay in the tree. In fact, they are the nodes that you assign to node.right, just before discarding that by setting node = null. Instead you should retain what you assigned to node.right, but return that instead.

Not wrong, but it is not necessary to have a condition in the else block: it is the only remaining possibility.

So do like this:

removeLessThan(node, value)

    if (node == null)
        return null
    
    if (node.value >= value)
        node.left = removeLessThan(node.left, value)
    else
        node = removeLessThan(node.right, value)
    
    return node

As to your statement that in the example BST "we traverse left all the way down to 5 and delete this node": this is not what should be happening. At the root we can see the node has a value 25 which is less than 30, so by consequence we know all nodes in the left subtree of the root are less than 30 too. We don't need to visit them!

We can immediately conclude that this left subtree can be removed without further inspection. Next, we should also get rid of the root node itself, and so we only continue with the right subtree of the root, where the process can repeat.