Citrix System Inc Interview Question
Software Engineer / Developersbool Search(Node *root, int a) {
if (root == NULL) {return false; }
if (root->no == a) {return true; }
for (int i=0; i< root->children.size(); i++) {
if (Search(root->children[i], a)) {
return true;
}
}
return false;
}
Node * LCA(Node *root, int a, int b)
{
if (root == NULL)
{
return NULL;
}
bool aFound = false, bFound = false;
Node *aParent = NULL;
Node *bParent = NULL;
for (int i=0; i < root->children.size(); i++) {
if (Search(root->children[i], a)) {
aParent = root->children[i];
aFound = true;
break;
}
}
for (int i=0; i < root->children.size(); i++) {
if (Search(root->children[i].no, b) {
bParent = root->children[i];
bFound = true;
break;
}
}
if (aFound == true && bFound == true) {
if (aParent != bParent) {
return root;
}
else {
return LCA(aParent, a, b);
}
}
else {
return NULL;
}
}
- Paras December 23, 2010