CareerCup

If p!=q, reduce to LCA problem
If p==q, DFS to find the parent of p

even in case of p==q its same as the lca

in both the cases => LCA problem

what does LCA means

does anyone knw the questions for technology Quality Analyst....i need dem vry urgent..plz tell asap....

suggest algo 4 lca

tree *least(tree *node,int val1,int val2)
{
tree *current=node;
while(1)
{
if(current->data<val1&&current->data<val2)
{
if(current->right->data==val1||current->right->data==val2)
return current;
else
current=current->right;
}
else if(current->data>val1&&current->data>val2)
{
if(current->left->data==val1||current->left->data==val2)
return current;
else
current=current->left;
}
else
return current;
}
}

@laasya1991
i think this code works only for binary search tree, and what if one value is present and one is not in our tree?

Btree* least(Btree *b ,int k1,int k2)
{
if(contains(b->lc,k1)&&contains(b->rc,k2) || contains(b->lc,k2)&&contains(b->rc,k1))
{
return b;
}
else if(contains(b->lc,k1)&&contains(b->lc,k2))
return least(b->lc,k1,k2);
else
return least(b->rc,k1,k2);
}

bool contains(Btree *bt,int k)
/* level order traversal to find whether node containing value k is present or not */
{
arrayQueue <Btree *> q; //queue of binary tree nodes
while(bt!=NULL)
{
if(bt->d==k)
return true;
//put bt's child on queue
if(bt->lc!=NULL)
q.push(bt->lc);
if(bt->rc!=NULL)
q.push(bt->rc);
//get next node to visit
try{
bt=q.front();
}
catch(queueEmpty){
return false;
}
q.pop();
}

}