Deleting a node in Binary Tree

Question

Below is the code I wrote for the case when the deleteItem is at the leaf node. Even if I am equating the found leaf node to "null" then also when I print the inorder traversing order if the tree, that element is not deleted and comes on the screen. What am I missing?

public void deleteNode(T deleteItem)
    {
        TreeNode<T> node = root;
        if(root == null)
        {
            System.out.print("Binary Tree does not exist");
            System.exit(0);
        }
        while((node.data != deleteItem) && (node.leftNode != null || node.rightNode != null))
        {
            if(deleteItem.compareTo(node.data)<0)
                node = node.leftNode;
            else
                node = node.rightNode;
        }
        //System.out.printf("deleting item is: %s\n", node.data);
        if(node.data != deleteItem)
        {   
            System.out.println("\ndeleteItem not found in the tree");
            System.exit(0);
        }
        else
        {
            if(node.leftNode == null && node.rightNode == null)
            {
                node = null;
            }
        }
    }

Kerollos Asaad · Accepted Answer · 2014-10-18 19:22:14Z

Java is "Pass-by-value", so TreeNode<T> tmp = root here means assigning tmp's references to root which means simply you have two different references to the same instance. According to that when you say node = null you set your local references to null which means that the node's parent is still reference to it. So to remove leaf node from the tree you need to keep track of its parent and then removing the reference to the node (removed the reference in the tree not you local copy) which will be something like that:

public void deleteNode(T deleteItem) {
        TreeNode<T> node = root;
        TreeNode<T> parent = null; // parent of the deleted node.
        if(root == null) {
            System.out.print("Binary Tree does not exist");
            System.exit(0);
        }
        while((node.data != deleteItem) && 
              (node.leftNode != null || node.rightNode != null)) {
            parent = node; // keep track of the parent of the deleted node
            if(deleteItem.compareTo(node.data) < 0)
                node = node.leftNode;
            else
                node = node.rightNode;
        }
        if(node.data != deleteItem) {   
            System.out.println("\ndeleteItem not found in the tree");
            System.exit(0);
        }
        else {
            if(parent.leftNode == node)
                parent.leftNode = null;
            else
                parent.rightNode = null;
        }
    }

Collectives™ on Stack Overflow

Deleting a node in Binary Tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related