Question about deleting a node from a binary tree (non-API binary tree; hand-coded)

[James Brooks]

Hi again,

I've got something that's been bugging me. For this binary tree deleteNode function, when a node is found, the method deleteFromTree is called on it. I understand everything, except: this may sound silly, but it seems that the method passes the target node on in a roundabout way. As you see, when found == true, we don't simply pass current as the method parameter, but rather tempCurrent.lLink or tempCurrent.rLink. Why is this? I know that there must be a reason that I'm not seeing (my text surely doesn't do it just for the heck of it), but it seems that this wastes computing time creating a reference to tempCurrent, then comparing it to deleteItem, then passing the appropriate child of tempCurrent to the deleteFromTree method, when current could simply be sent as the parameter, as it is the target node upon found == true. Thanks in advance!

  

    public void deleteNode(T deleteItem)
    {
        BinaryTreeNode<T> current;  
        BinaryTreeNode<T> trailCurrent; 
        boolean found = false;

        if (root == null)
            System.err.println("Cannot delete from an "
                             + "empty tree.");
        else
        {
            current = root;
            trailCurrent = root;

            while (current != null && !found)
            {
                if (current.info.equals(deleteItem))
                    found = true;
                else
                {
                    trailCurrent = current;

                    Comparable<T> temp =
                              (Comparable<T>) current.info;

                    if (temp.compareTo(deleteItem) > 0)
                        current = current.lLink;
                    else
                        current = current.rLink;
                }
            }

            if (current == null)
                System.out.println("The delete item is not in "
                                 + "the tree.");
            else if (found)
            {
                if (current == root)
                    root = deleteFromTree(root);
                else
                {
                    Comparable<T> temp =
                             (Comparable<T>) trailCurrent.info;

                    if (temp.compareTo(deleteItem) > 0)
                        trailCurrent.lLink =
                              deleteFromTree(trailCurrent.lLink);  //why not just send current instead of tempCurrent.appropriateChild?
                    else
                        trailCurrent.rLink =
                              deleteFromTree(trailCurrent.rLink);
                }
            }
        }
    }
  

[Martijn Verburg]

This is a great question for experimenting!

So, have you tried passing in current? What happens? See if you can print out the tree before and after in both cases (using the existing way and you're passing in current way). Use a small tree but make sure it as a depth of at least 3-4 so you can test deleting root, leaf, 'ordinary node with parent and children'.

Let us know how you get on!

[James Brooks]

Martijn Verburg wrote:This is a great question for experimenting!

So, have you tried passing in current? What happens? See if you can print out the tree before and after in both cases (using the existing way and you're passing in current way). Use a small tree but make sure it as a depth of at least 3-4 so you can test deleting root, leaf, 'ordinary node with parent and children'.

Let us know how you get on!

Sorry about the double post, it didn't look like it took the first time. I plan to do that, and I'll be back later today with the results after work.

[Martijn Verburg]

Patrick Brooks wrote:Sorry about the double post, it didn't look like it took the first time. I plan to do that, and I'll be back later today with the results after work.

No probs, we've been experiencing a few glitches of late