Find the least common parent in a binary tree?

Question

This question might have been asked by a lot of guys but, it is kinda different. We have a binary tree. And you are given two nodes p & q. We have to find the least common parent. But you dont have root node pointer which points to the root. You are provided with two inbuilt functions which are:

1) BOOL same(node *p, node *q); -> returns true if the nodes are same or else false.

2) node* parentNode(node *c); -> returns a node which is the parent of the current node.

If the node c is actually root then parentNode function will return you with aNULL value. Using the functions we have to find the least common parent of the tree.

Answer 1

Assuming C++:

node* leastCommonParent(node *p, node *q)
{
    node *pParent = parentNode(p);
    while(pParent != 0)
    {
        node *qParent = parentNode(q);
        while(qParent != 0)
        {
            if (0 == same(pParent, qParent))
                return pParent;
            qParent = parentNode(qParent);
        }
        pParent = parentNode(pParent);
    }
    return 0;
}

UPDATE: A version without explicitly declared variables using recursion follows. I'm sure it can be improved and would probably never use it in production code in the current form.

node* qParent(node *p, node *q)
{
    if (p == 0 || q == 0)
        return 0;
    if (same(p, q) == 0)
        return p;
    return qParent(p, q->parent);
}

node* pParent(node *p, node *q)
{
    return qParent(p, q) ? qParent(p, q) : pParent(p->parent, q);
}

node * result = pParent(p, q);

Answer 2

Step1: Using parentNode function find the distance d1 of the node p from root. similarly find distance d2 of node q from the root. (say, d2 comes out ot be greater than d1)

Step 2: Move the farther node(whose ever d-value was greater) pointer d2-d1 steps towards root.

Step3: Simultaneously move pointers p and q towards root till they point to same node and return that node.

Basically it will be like finding the merge point of two linked-lists.
Check the below link: Check if two linked lists merge. If so, where?

Time complexity: O(N)
Your code would look somewhat along the lines:

node* LCP(node* p, node *q){
    int d1=0, d2=0;
    for(node* t= p; t; t = parentNode(p), ++d1);
    for(node* t= q; t; t = parentNode(q), ++d2);
    if(d1>d2){
        swap(d1, d2);
        swap(p, q);
    }
    for(int i=0; i<(d2-d1); ++i)
        q = parentNode(q);
    if( same(p, q)){
        return parentNode(p);
    }
    while( !same(p, q)){
        p = parentNode(p);
        q = parentNode(q);
    }
    return p;
}