Check the c language implementation:
node* LeastCommonAncestor(const node* root, const int data1, const int
data2, int* const status){
static node* ans = NULL;
int l_st=0, r_st=0;
if(root==NULL) return;
if(root->left != NULL)
LeastCommonAncestor(root->left, data1, data2, &l_st);
if(root->right != NULL)
LeastCommonAncestor(root->right, data1, data2, &r_st);
if(l_st == 3 || r_st == 3)//if both data already found by subtrees
return ans;
if((l_st|r_st)==3){//if one data found in each subtree
*status = 3;
ans=root;
return ans;
}
if( ((l_st|r_st)==2 && root->data == data1) || ((l_st|r_st)==1 &&
root->data == data2) ){
//if one data found in subtree and other is root itself
ans = root;
*status =3;}
else//record if any one data found (case when both data found is
catered above)
*status |= l_st |= r_st;
if(root->data == data1)
*status |= 1;
if(root->data == data2)
*status |= 2;
return ans;
}
Full Program here:
https://github.com/monish001/CPP-Programs/blob/master/General/LeastCommonAncestor.c
Program tested on Dev-CPP
-
Monish
On Aug 9, 7:56 pm, Raman <[email protected]> wrote:
> Can anyone give me the recursive algo to find closest ancestor of two nodes
> in a tree(not a BST).
--
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.
