0

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);
    }

}
1
  • Do you must follow that method signature or is something you came up with? Commented Apr 27, 2013 at 15:17

1 Answer 1

5

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.

1
  • Yes that helped. Thank you. As java is pass by value, it cant happen through parameters but when we take a reference inside the function for the object we want to edit, then it is possible. Commented Apr 28, 2013 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.