Finding the parent of a node in a Binary tree

Question

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…

Accepted Answer

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);
            }
        }
    }
}  
```

Finding the parent of a node in a Binary tree

Solution

Problem