CareerCup

node* lca(node *temp1)
{
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);
}
}

sorry....the line:

if(!found)lca(parent);

should be outside the while loop....
basically wat i am doing is going to the parent of temp1 and searching for the other node(temp2) and repeating this process

//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;
}
}

/* 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);
          }

}

TreeNode* LCA(TreeNode* root, int p, int q)
{
   if (root == NULL) return NULL;
   if (root->val == p || root->val == q) return root;
   TreeNode* l = LCA(root->left, p, q);
   TreeNode* r = LCA(root->right, p, q);
    return l&&r ? root  : l ? l : r;
      
}