Question: "Binary Tree" only with parent pointer

[outlaw525]

Hi,

The fuction should work in C.

I need to create a struct for tree with pointer to parent only, without pointers to left & right childs.

The function got two pointers for two childs and printer the shared parent of them.

The function will print the info of the shared parent.

I attached a doc file that show what I want, there is two blue childs that the red parent is the one that the function need to print.

I alse need to know the struct elements.

Sorry for my english.

Thanks alot

[WingedPanther]

Instead of thinking of this as a Binary Tree, flip the image upside down and think of it as a linked list with multiple roots that eventually merge.

[dargueta]

Since both children have the same parent (eventually), just compare the parents recursively, like so:

struct Node
{
    Node  *parent;
    int  value;
};
 
Node *getParent(Node *childLeft, Node *childRight)
{
    Node *currLeft = childLeft;
    Node *currRight = childRight;
 
    while(true)
    {
        //check for nulls
        if((currLeft == NULL)||(currRight = NULL))
            return NULL;
        //check to see if the parents are the same
        //if so, return the parent.
        if(currLeft->parent == currRight->parent)
            return currLeft->parent;
        //parents aren't the same, continue up the tree
        currLeft = currLeft->parent;
        currRight = currRight->parent;
    }
}