how about this:-
int leastCommanAncestor(struct node* root, int n1, int n2)
{
if(root==NULL)
return -1;
if(root->data>n1 && root->data>n2)
return leastCommanAncestor(root->left,n1,n2);
else if(root->data<n1 && root->data<n2)
return leastCommanAncestor(root->right,n1,n2);
return root->data;
}
correct if wrng
On Sun, Oct 28, 2012 at 9:40 PM, rahul sharma <[email protected]>wrote:
> According to wiki http://en.wikipedia.org/wiki/Least_common_ancestor
>
> n1 is parent of n2 then n1 is lca....but according to above algo return
> -1..i have taken it from(http://www.geeksforgeeks.org/archives/1029)
>
> plz tell if it is corerct....in 2 doubts
>
> 1. if n1is parent of n2
> 2. if n2<n1
>
> will above algo works???I think No.
>
> So will add the one more condtion for n2<n1..but do we require to return
> -1 if n2 is child of n1 ???or n1 itself?
>
>
> On Sun, Oct 28, 2012 at 9:25 PM, rahul sharma <[email protected]>wrote:
>
>> an one doubt that if we have to find lca of n1 and n2...then if say n1 is
>> parent of n2..in this case we would return n1 or n1->parent.....
>>
>>
>> and if n1 is the root and n1 is child then(n1 has no parent)..we will
>> return n1 or -1????
>>
>>
>> On Sun, Oct 28, 2012 at 9:18 PM, rahul sharma <[email protected]>wrote:
>>
>>> I think th efollowing code lacks one statement i.e if(root->data<n1 &&
>>> root->data >n2)
>>> Correct me if wrng
>>> int leastCommanAncestor(struct node* root, int n1, int n2)
>>> {
>>>
>>> if(root == NULL || root->data == n1 || root->data == n2)
>>> return -1;
>>>
>>>
>>> if((root->right != NULL) &&
>>> (root->right->data == n1 || root->right->data == n2))
>>> return root->data;
>>> if((root->left != NULL) &&
>>> (root->left->data == n1 || root->left->data == n2))
>>> return root->data;
>>>
>>> if(root->data > n1 && root->data < n2)
>>> return root->data;
>>> if(root->data > n1 && root->data > n2)
>>> return leastCommanAncestor(root->left, n1, n2);
>>> if(root->data < n1 && root->data < n2)
>>> return leastCommanAncestor(root->right, n1, n2);
>>> }
>>>
>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
