Zynga Interview Question
Country: United States
Hello : it does not matter whether you are finding LCA of a btree or a bst, the concept is same, and the concept is :
Assumption : two values are given
1. start from the root node,
2. search where these two vales lies,
2.1 if they lies(means these two values are present) in two different node, then print current node as answer, if one of these two vales are not present then print -1
2.2 if they lies in same node, go to that node and keep parent node also, because if these two values found in new node then parent will be the answere, other wise go to 2 again
tree * LCA(tree * root, int num1, int num2)
{
if(root ==NULL)
retrun root;
else
{
if((root->data == num1) ||(root->data ==num2))
return root;
else
{
tree* left = LCA(root->left,num1,num2);
tree* right = LCA(root->left,num1,num2);
if(left && right)
return root;
else if(left)
return left;
else if(right)
return right;
else
return NULL;
}
}
}
The idea is to check for each given node in tree about whether it lies left or right of a given node.
-------------------------------------------------------------------------
struct node{
int data;
struct node* left;
struct node* right;
};
int isInTree(struct node* root, int node)
{
if(root == NULL)
{
return 0;
}
if(root->data == node)
{
return 1;
}
return (isInTree(root->left, node) || isInTree(root->right, node));
}
int findLCA(struct node* root, int node1, int node2)
{
if(root == NULL)
{
return 0;
}
int isNode1InLeft = isInTree(root->left, node1);
int isNode2InLeft = isInTree(root->left, node2);
if(isNode1InLeft != isNode2InLeft)
{
return root;
}
return (isNode1InLeft ? findLCA(root->left, node1, node2) : findLCA(root->right, node1, node2));
}
Wanted to add the solution that does not involve the recursion and requires a bit of additional space(2 strings):
Tree.prototype.lowestCommonAncestor = function(data1, data2){
var root = this.root;
function getPath(data){
return (function find(node, path){
if(!node)
return null;
if(node.data == data)
return path;
var left = find(node.left, path+'0');
var right = find(node.right, path+'1');
if(left)
return left;
if(right)
return right;
return null;
})(root, '');
}
var path1 = getPath(data1);
var path2 = getPath(data2);
if(!path1 && !path2)
return null; //nodes do not exist
var lca = this.root;
var i = 0;
while(i<path1.length && i<path2.length && path1[i]==path2[i]){
if(path1[i]==='0')
lca = lca.left;
else
lca = lca.right;
i++;
}
return lca;
};
The idea is to traverse the tree in pre-order, so
you compare the current node with the values you are looking for, then you call the function with the left and right value.
so when the left and right children return both 1 OR when one of them return 1 and the current node is one of the values then the current node is the least common ancestor.
the code is something like this:
- Franky January 15, 2013