CODEWITHSUNDEEP
javabinary-search-tree
Yatin Garg
Yatin Garg

Reputation: 141

How to remove from a binary search tree?

I found on many sites following code to remove a node from a binary search tree for java. Te problem what I have with this code is that when the element to be removed is found out, after that in one of the case it is tried to gove pos the null value. Now as we are calling this method recursively I think the actual pos will not get set to null. Please let me know if I am right about it 

public void remove (String key, BSTNode pos)
{
    if (pos == null) return;
    if (key.compareTo(pos.key)<0)
        remove (key, pos.leftChild);
    else if (key.compareTo(pos.key)>0)
        remove (key, pos.rightChild);
    else {
        if (pos.leftChild != null && pos.rightChild != null)
        {
            /* pos has two children */
            BSTNode maxFromLeft = findMax (pos.leftChild); //need to make a findMax helper 
            //"Replacing "  pos.key " with " maxFromLeft.key
            pos.key = maxFromLeft.key;
            remove (maxFromLeft.key, pos.leftChild);
        }
        else if(pos.leftChild != null) {
            /* node pointed by pos has at most one child */
            BSTNode trash = pos;
            //"Promoting " pos.leftChild.key " to replace " pos.key
            pos = pos.leftChild;
            trash = null;
        }
        else if(pos.rightChild != null) {
            /* node pointed by pos has at most one child */
            BSTNode trash = pos;
            /* "Promoting " pos.rightChild.key" to replace " pos.key */
            pos = pos.rightChild;
            trash = null;
        }
        else {
            pos = null;
        }
    }
}

Upvotes: 0

Views: 116

Answers (2)

triadiktyo
triadiktyo

Reputation: 489

You are right. The pos will not be set to null. It is simply changing the value of the local variable pos in the current stack frame but as soon as you return from that recursion level the change will not be persisted.

Upvotes: 1

RockAndRoll
RockAndRoll

Reputation: 2287

yes you are right. Actual pos will not be set as null.

Reason

Since its recursion.for every recursive call,pos is different.So once the node is found out,it will check whether it has left or right child.As per code shared by you,when the node does not have left and right child,it will be set as null which is correct.

In short,if the node you want to delete is a leaf node,it will be set as null.

Note: There are some more changes that will be needed in your code.To start with i would say you need to return pos at last and will have to assign it while calling delete method recursively like this.

pos.leftChild=remove (maxFromLeft.key, pos.leftChild);

Upvotes: 1

Related Questions