Facebook Interview Question: LCA problem with no parent po... | Glassdoor

## Interview Question

Software Engineering Intern Interview

# LCA problem with no parent pointers. Given the root of a

tree and pointers to two nodes contained in that tree, return the lowest common ancestor of the two nodes. IE, the common ancestor furthest from the root.

0

Was the data structure a binary tree or a binary search tree?

Anonymous on Apr 26, 2014
0

The complexity in both cases remaining O(n) though for BST the search for the LCA becomes quite easy.

Srikant Aggarwal on Oct 24, 2014
0

bool printCommonAncestor(struct node* node,int x,int y)
{
if (node == NULL)
return false;

// first recur on left subtree
bool left = printCommonAncestor(node->left,x,y);
bool right = printCommonAncestor(node->right,x,y);

if(left && right)
printf("%d ", node->data);

if(left || right)
{
if(node->data == x || node->data==y)
{
printf("%d ", node->data);
}
return true;
}

if(node->data == x || node->data==y)
return true;

return false;

// now deal with the node

}

Do a Post order traversal. If its on left and right of the tree then return that node

Anonymous on Mar 3, 2016
0

Array of 256 chars for each string. Assign to 0. Then as a character comes increment the count.
Compute a hash key using these 256 values and store the hash key->String mapping.
Do so for each string, if the mapping already exists, add this string to the list of strings for this mapping.

Anonymous on Mar 3, 2016