Objects differ, but get trough .equals function and '==' operator

Question

I'm filling up a binary tree, and afterwards I try to get the parent of a certain leaf, trough a recursive method. Each node contains the String data; and let's say i'll only initialize the String data with "*" for each leaf. In that method, i'm traversing trough the tree, until the given node(leaf) has been found, so I can return the parent. After finding a leaf, I want to check if the node(leaf) is identical to the target I was searching for. Sadly, this is not the case, and the method returns the parent first found leaf. I have used .equals() method and the "==" operator, but none of them work. Does anyone know how to solve this problem?

    BinaryNode root = new BinaryNode("root",2);
    BinaryNode na = new BinaryNode("a",2);
    BinaryNode naLeaf1= new BinaryNode("*",0);
    BinaryNode naLeaf2 = new BinaryNode("*",0);
    na.addChild(naLeaf1);
    na.addChild(naLeaf2);
    BinaryNode nb = new BinaryNode("b",2);
    BinaryNode nbLeaf1= new BinaryNode("*",0);
    BinaryNode nbLeaf2 = new BinaryNode("*",0);
    nb.addChild(nbLeaf1);
    nb.addChild(nbLeaf2);
    root.addChild(na);
    root.addChild(nb);

This is the recursive method that traverses trough the binary tree.

public BinaryNode getParent(BinaryNode root, BinaryNode target) {

    if(root!=null) {
        for(BinaryNode ni: root.childeren) {
            if(!ni.data.equals("*")) {
                return  getParent(ni, target);
            }else  {
                if(ni.equals(target)) {
                    return  root;
                }
            }
        }
    }
    return root;
}

I have added an override for the .equals method, but that doesn't seem to solve the problem.

@Override
public boolean equals(Object target) {
    if(target==null) return false;
    if(target==this) return true;
    if(!(target instanceof BinaryNode)) return false;
    return false;
}

Does BinaryNode override the default equals() implementation? If so, can you show it? — David ten Hove, Dec 06 '14 at 15:02
@DavidtenHove, I haven't implemented an override. I'll be doing that right away. Thanks ! — gdm, Dec 06 '14 at 15:04
@DavidtenHove, i have added the override, but that doesn't seem to solve the problem. Isn't there a way of checking the object's reference? — gdm, Dec 06 '14 at 15:12

score 2 · Accepted Answer · answered Dec 06 '14 at 16:14

Your problem is not the ´equals´ method, but the algorithm you use. First of all, doesn't the BinaryNode have the parent as a field? If not, then seriously consider adding that.

If you really do not want each node to know its parent, then you need to traverse the full tree, and not just one branch. Something like the following:

public BinaryNode getParentOf(BinaryNode target) {

    for(BinaryNode child: children) {
        if (child == target) {
            return this;
        }
        BinaryNode result = child.getParentOf(target);
        if (result != null ) {
            return result;
        }
    }
    return null;
}

But seriously, make sure each node knows its parent.

You're right about the algorithm, and I took care of it. I also added the parent-property to the BinaryNode class. Thanks alot ! — gdm, Dec 06 '14 at 16:23

score 1 · Answer 2 · answered Dec 06 '14 at 15:31

1

In your .equals() override you'll need to do some calculation of what exactly separates two such objects. How about doing a check of the parameters you feed it, that way the objects are equal if their root and target are the same.

answered Dec 06 '14 at 15:31

kinbiko

2,066
1
28
40

score 0 · Answer 3 · answered Dec 06 '14 at 15:37

Look at the first if condition !ni.data.equals("*"). This evaluates to false, right? Because you set data to '*' for all leafs. This ni.equals(target) evaluates to false as well, because there is nothing wrong with your equals method, and it works as expected. This happenes for all children, you get out of the loop, and return root.

You need to rethink the logic of this function, it is just wrong. There is nothing wrong with the equals though (and you don't need to override it like this, could just use ==).

Objects differ, but get trough .equals function and '==' operator

3 Answers3