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 what I am trying to do in order to find the parent node is logically correct.

Solution 1

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

Solution 2

I compared value to value because I didn't define the way to compare the nodes.

    public static Node FindParent(Node root, Node node)
    {
        if (root == null || node == null)
        {
            return null;
        }
        else if ( (root.Right != null && root.Right.Value == node.Value) || (root.Left != null && root.Left.Value == node.Value))
        {
            return root;
        }
        else
        {
            Node found = FindParent(root.Right, node);
            if (found == null)
            {
                found = FindParent(root.Left, node);
            }
            return found;
        }
    }

Solution 3

Use two parameters: One for the current node and one for the node being searched.