removeAll method for BST (Binary Search Tree)

Question

I have this code below, I'm attempting to create a removeAll method for a Binary Search Tree. I think the code below is most likely readable even without all the outside code and context, but if not, I'll be glad to provide more information. However, this code is simply not working and I cannot figure out the reason for it. I am just trying to iterate through the binary search tree using an in-order traversal, counting the number of times the targetElement exists, and then calling the remove method that number of times.

public void removeAllOccurrences(T targetElement) throws ElementNotFoundException 
   {
    removeElement(targetElement);

    Comparable<T> comparableElement = (Comparable<T>) targetElement;
    Iterator<T> iter = iteratorInOrder();
    int n = 0; 


    while(iter.hasNext())
    {
        if (((Comparable<T>) comparableElement).equals(iter.next())) 
        {
            n++;
        }
    }

    for(int i=0; i<n; i++)
    {
        removeElement(targetElement);
    }


}

The name of the class is LinkedBinarySearchTree. We are working with BinaryTreeNode. We have a getRootNode() method.

Answer 1

Since you are making the assumption that T implements Comparable<T> (by casting targetElement) you should use this functionality. The equals method you are using to compare comparableElement and iter.next() is a method inherited from the Object class and may not have been overridden by T. The default implementation of the equals method simply compares the memory addresses of the caller and the argument which is probably not what you want.

The compareTo method of Comparable<T> would actually be implemented by T so you should use it instead. compareTo returns an int which indicates the caller is less than the argument if it is negative, the caller is greater than the argument if it is positive, or the caller is equal to the argument if it is zero. Therefore, you should change the expression ((Comparable<T>) comparableElement).equals(iter.next()) to comparableElement.compareTo(iter.next()) == 0. The casting of comparableElement isn't necessary because the variable is already of type Comparable<T>.

Here is how the change looks in your code.

public void removeAllOccurrences(T targetElement) throws ElementNotFoundException {
    removeElement(targetElement);

    Comparable<T> comparableElement = (Comparable<T>) targetElement;
    Iterator<T> iter = iteratorInOrder();
    int n = 0;

    while(iter.hasNext()) {
        if (comparableElement.compareTo(iter.next()) == 0) {
            n++;
        }
    }

    for (int i = 0; i < n; i++) {
        removeElement(targetElement);
    }
}

Let me know if I have misunderstood your question.