Node Reference in Binary Tree

Question

So I want to go into my tree (which is assumed to have no duplicates and is branched correctly) and find the element that is given in the parameters. I have found that my method gives me a BinaryNode that resembles what I want (the root) in its fields, but is not actually the root. I have not overridden the equals method. Using the equals method, the test returns false when the returned object and the root are compared. I want to know why my variable, elementNode, does not reference (and hence change) the root to be null when it is set null.

Binary nodes are implemented with generics. This method is being called with the root as its starting point. Any help will be appreciated, thank you.

/**
 * Returns the node that the sought element resides within
 * 
 * @param element: The element being hunted
 * @param start: The start of the search (usually the root)
 * @return The node that the element resides in
 */
private BinaryNode<T> findElementNode(T element, BinaryNode<T> start) {


    if (start.getElement().equals(element)) {
        return start;
    }

    // the element is not in the collection
    if (start.getLeftChild() == null && start.getRightChild() == null) {
        return null;
    }

    int comparison = element.compareTo(start.getElement());

    if (comparison < 0) {
        return findElementNode(element, start.getLeftChild());
    } else {
        return findElementNode(element, start.getRightChild());
    }
}

EDIT FOR EXAMPLE: (this is for a removal method)

    if (!hasLeft && !hasRight) {

        System.out.println(elementNode + "," + root);
        elementNode = null;         
        System.out.println(elementNode + "," + root);

        return true;
    }

This outputs:

BinaryNode@68b0019f,BinaryNode@68b0019f and null,BinaryNode@68b0019f

EDIT FOR ANSWER: The reason that the returned element does not set the node it points to as null is because in Java, we can only point at, not edit, memory locations. So in order to make my node null, I will locate the parent and just set its left/right child to null.

"I know this because the root field (a member of the tree) is what I was searching for and it is not equal to the found item, even though all the fields hold the same values." Could you show us a little example demonstrating the problem ? And did you override the equals method in your object's class that your tree holds? — Alexis C.
I forgot to add that I've hunted for information about these, but my question seems too specific. I think the error is small and that I'm just overlooking something obvious — shane
Currently this will fail for any non-perfectly-balanced tree - you need to check if start is null, or only call findElementNode recursively for children which exist. Other than that, it looks okay - a short but complete example would be useful. It's not even clear what you mean in the description of what's wrong... — Jon Skeet
John & ZouZou: I added that check and an example of my test and clarified my explanation — shane

Vannens Vannens · Accepted Answer · 2014-01-02T10:10:43

Try with something like this.

private boolean findElementNode(T element, BinaryNode<T> start) {

    if (start == null) {
       return false;
    } else {
      if (element.getElement().equals(start.getElement())) {
         return true;
      } else {
         int comparison = element.compareTo(start.getElement());

         if (comparison < 0) {
            return findElementNode(element, start.getLeftChild());
         } else {
            return findElementNode(element, start.getRightChild());
         }          
     }
}

EDIT: this is actually what you want. Tell me if this works.

private BinaryNode<T> findElementNode(T element, BinaryNode<T> start) {
    if(start != null){
        if(start.getElement().equals(element)){
           return start;
        } else {
            BinaryNode<T> start = findElementNode(element, start.getLeftChild());
            if(start == null) {
                start = findElementNode(element, start.getRightChild());
            }
            return start;
         }
    } else {
        return null;
    }
}

Node Reference in Binary Tree

1 Answers