Traverse a leftist tree

[HG319]

I am given a problem where I need to search for any element in the leftist heap, not the min. I am having trouble solving this problem. We were told to create a parent pointer and that will help us traverse.

Does anyone have any ideas?

[Duthomhas]

All trees are composed of nodes. A node has some number of children, and it also has a parent. (The root node's parent is nullptr, as it has no parent.)

Given node (1)=A with children (2)=B and (3)=C, and I wish to find C, I can look at node (1) and see A≠C, you have a choice of which node to check next. Move to (2): B≠C. Now (2) has no children, you must move back to (2)'s parent so that you can go to (3) and discover C=C.

[HG319]

Traversing through an AVL tree and Binary are easy to me, I was trying to figure out how to incorporate the parent node in but I am stuck.
Here is my Avl search, hope you can help me a little more

(Typedef Tree, calls is AvlNode)

bool contains( const Tree  & x, AvlNode *t ) const
    {
        if( t == nullptr )
            return false;
        else if( x < t->element )
            return contains( x, t->left );
        else if( t->element < x )
            return contains( x, t->right );
        else
            return true;    
    }

I was thinking something like this for the heap search

if(t==nullptr){
            return false;
       }
       else if(t->left->element==x){
            return true;
       }
       else if(t->right->element==x){
            return true;
       }
       else if(t->right->element!=x){
            return Find(x, t->left);
       }
       else
        return true;