Adobe Interview Question
Software Engineer / Developers//C#
Node LCA( Node head, Node n1, Node n2)
{
if (head != null)
{
// Assume Find API is implemented such that
// 1 if n1 and n2 are present
// -1 if n1 and n2 both are not present
// 0 if either one is present but not both
int i = Find(head.Left, n1, n2);
if ( i == 0)
{
return LCA(head.Right, n1, n2);
}
else if ( i == 1)
{
return LCA(head.Left, n1, n2);
}
else
return head;
}
else
{
return null;
}
}
//C#
Node LCA( Node head, Node n1, Node n2)
{
if (head != null)
{
if (head == n1 || head == n2)
return head;
// Assume Find API is implemented such that
// 1 if n1 and n2 are present
// -1 if n1 and n2 both are not present
// 0 if either one is present but not both
int i = Find(head.Left, n1, n2);
if ( i == -1)
{
return LCA(head.Right, n1, n2);
}
else if ( i == 1)
{
return LCA(head.Left, n1, n2);
}
else
return head;
}
else
{
return null;
}
}
/* BST version */
Node * LCA( Node *root, Node *a, Node *b )
{
if ( root->data > a && root->data > b )
return LCA ( root->left, a, b );
else if ( root->data < a && root->data < b )
return LCA ( root->right, a, b );
else
return root ;
}
/* Non-BST version */
Node *LCA( Node *root, Node *a, Node *b )
{
if ( cover(root->left, a) && cover(root->left, b) )
return LCA( root->left, a, b) ;
else if ( cover(root->right, a) && cover(root->right, b) )
return LCA(root->right, a, b);
else
return root;
}
bool cover( Node *root, Node *x )
{
if ( root == NULL )
return false;
if ( root == x )
return true;
return cover(root->left, x) || cover(root->right, x) ;
}
int search(node * root, int & val){
if(root!=NULL){
if(search(root->left,val)) return 1;
if(root->key==val) return 1;
if(search(root->right,val)) return 1;
}
return 0;
}
int flag=0,found=0,f_val;
node *common=NULL;
void common_ancestor(node * root, int & val1, int & val2){
if(root==NULL) return;
common_ancestor(root->left,val1,val2);
if(flag==0){
if(root->key==val1){
f_val=val2;
flag=1;
}
else if(root->key==val2){
f_val=val1;
flag=1;
}
}
if(flag==1){
if(found==0){
if(root->key==f_val || search(root->right,f_val)){
common=root;
found=1;
}
}
return;
}
common_ancestor(root->right,val1,val2);
}
//first determine which value is smaller say that left and other one right
int lca(node *ptr,int data,node *old)
{
if(ptr==null)
return false;
else if(ptr->data==left&&flag==0)
{
flag=1;
ansestor=ptr;
while(! (search(ptr->right,ptr))
ancestor=old;
return ancestor;
}
else if(ptr->data==right)
return true;
else
{
search(ptr->left,ptr);
search(ptr->right,ptr);
}
}
node* lca(node *temp1)
- trojansmith August 08, 2011{
parent=temp1->parent;
temp=parent;
while(temp2->element!=temp->element)
{
if(temp2->element>temp->element) temp=temp->right;
else if(temp2->element<temp->element) temp=temp->left;
else if(temp2->element==temp->element){ found=1;return parent;}
if(!found)lca(parent);
}
}