sam_rox sam_rox -4 years ago 69
Java Question

Finding the parent of a node in a Binary tree

I am trying to write a method to find the parent of a given node. Here's my method.

I created a

BinaryNode
object r which initially refers to root.

public BinaryNode r=root;
public BinaryNode parent(BinaryNode p){
BinaryNode findParent=p;
if (isRoot(findParent) || r==null){
return null;
}
else{
if(r.left==findParent || r.right==findParent)
return r;
else{
if (r.element<findParent.element)
return parent(r.right);
else
return parent(r.left);
}
}
}


THis code doesn't work properly .I think that's because r is a null object.Because when I do

if (isRoot(findParent) || r==null){
System.out.println(r==null);
return null;}


r==null
evaluates to
true
.How come that happen because I have inserted nodes as

public static void main (String args[]){
BinaryTree t=new BinaryTree();
t.insert(5);
t.insert(t.root,4);
t.insert(t.root,6);
t.insert(t.root,60);
t.insert(t.root,25);
t.insert(t.root,10);


and the root is not null.

Can some one please point out why that happens and if what I am trying to do in order to find the parent node is logically correct.

Answer Source

The problem is that you MUST keep track of your current node, while keeping the node who's parent you want to find. And as far as I understand your code, you keep the variable, but never change it
I'd recommend using a helper function. This would look something like that:

public BinaryNode parent(BinaryNode p){
    parentHelper(root,p)
}
private BinaryNode parentHelper(BinaryNode currentRoot, BinaryNode p) {        
    if (isRoot(p) || currentRoot==null){
            return null;
    }
    else{
        if(currentRoot.left==p || currentRoot.right==p)
            return currentRoot;
        else {
            if (currentRoot.element<p.element) {
                return parentHelper(currentRoot.right,p);
            }
            else {
                return parentHelper(currentRoot.left,p);
            }
        }
    }
}  
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download