Java – Implementing Delete a Node in Binary Search Tree

binary-search-treejava

Trying to delete a node from BST. After the execution, the node still persists in the tree. How can I implement it properly?

public void deleteNode(TreeNode removeNode, TreeNode root)
{


    if(removeNode.Left==null && removeNode.Right==null) //0 children
    {
        removeNode = null;
    }
    else if(removeNode.Left==null)//1 children
    {

        removeNode = removeNode.Right;
    }
    else if(removeNode.Right==null)//1 children
    {
        removeNode = removeNode.Left;
    }
    else // 2 children
    {
        int successorValue = this.getSuccessor(removeNode, root);
        TreeNode successor = this.search(successorValue,root);

        removeNode.data = successor.data;

        deleteNode(successor, root);
    }

}

Best Solution

The node is still there because you never remove it from the tree.

When you call deleteNode you get a reference to the node you want to delete and the root of the tree. When you say removeNode = null; you set your reference to null, you don't remove the object. This means the nodes in the tree still reference that node.

To remove the node from the tree you need to remove the references to the node. I don't now what methods you have available, but to send you in the right direction it should be something like this:

public void deleteNode(TreeNode removeNode, TreeNode root)
{
    TreeNode parent = removeNode.getParent();   //Find parent node to removeNode.

    if(removeNode.Left==null && removeNode.Right==null) //0 children
    {
        if(parent.Left.equals(removeNode))
             parent.Left = null;                //Set the parents reference to null. 
        else
             parent.Right = null;
    }
    else if(removeNode.Left==null)//1 child
    {
        if(parent.Left.equals(removeNode))
             parent.Left = removeNode.Right;  //Reassign the parents reference to the correct node. 
        else
             parent.Right = removeNode.Right;
    }
    ... //etc.

The point is you have to change the references in the tree and not your local reference. Hope this makes sense.

Related Question