@Anchal....thanks for pointing out the error...i found where the error is...it is the else loop in this line in this checking...
if(p1->right == cur1 || p2->left == cur2) actually before i have already assigned p1->right == cur1 (or p2->left=cur2)..it shud have been in else loop..soryy for the mistake..i will submit the modification asap.. On 7/11/11, aanchal goyal <[email protected]> wrote: > @Piyush.. > I tried your algo on BST {5,4,6,3,2,1,8,7,10,12,9,11}. > Its only returning 1+7. > Other pairs are 5+3, 6+2. > > On Mon, Jul 11, 2011 at 6:56 PM, Piyush Sinha > <[email protected]>wrote: > >> @Aanchal....I think my following algo will work..its a modification of >> Morris traversal...check if you can find any bug in it...I have tried my >> best to make it error free..For further details regarding Morris >> traversal, >> check out http://geeksforgeeks.org/?p=6358 >> >> *void findsum(node *T,int key) >> { >> int n = countnodes(T);//returns the number of nodes in the BST >> int i=0; >> int j=n-1; >> node *cur1,*cur2,*p1,*p2; >> cur1=cur2=T; >> int flag1,flag2,sum; >> flag1=flag2=1; >> while(i<j) >> { >> if(cur1->left == NULL && cur2->right == NULL) >> { >> sum = checksum(cur1,cur2,key); >> if(sum==0) //if cur1->data + cur2->data ==key >> { >> i++;j--; >> flag1=flag2=1; >> cur1 = cur1->right; >> cur2 = cur2>left; >> } >> if(sum>0) //if cur1->data + cur2->data > key >> { >> cur2 = cur2->left; >> flag1 = 0; //do not do anything with the left >> traversal >> j--; >> } >> if(sum<0) //if cur1->data + cur2->data <key >> { >> cur1 = cur1->right; >> flag2 = 0;//do not do anything with the right >> traversal >> i++; >> } >> } >> else >> { >> if(flag1 && cur1->left!=NULL) >> { >> p1 = cur1->left; >> while(p1->right!=NULL && p1->right!=cur1) >> p1 = p1->right; >> if(p1->right == NULL) >> { >> p1->right = cur1; >> cur1 = cur1->left; >> } >> } >> if(flag2 && cur2->right!=NULL) >> { >> p2 = cur2->right; >> while(p2->left!=NULL && p2->left!=cur2) >> p2 = p2->left; >> if(p2->left == NULL) >> { >> p2->left = cur2; >> cur2 = cur2->right; >> } >> } >> if(p1->right == cur1 || p2->left == cur2) >> { >> sum = checksum(cur1,cur2,key); >> if(sum==0) //if cur1->data + cur2->data ==key >> { >> if(cur1->left == NULL) >> { >> cur1 = cur1->right; >> flag1 = 0; >> } >> else if(p1->right == cur1) >> { >> p1->right = NULL; >> cur1 = cur1->right; >> flag1 = 1; >> } >> >> if(cur2->right == NULL) >> { >> cur2 = cur2->left; >> flag2 = 0; >> } >> else if(p2->left == cur2) >> { >> p2->left = NULL; >> cur2 = cur2->left; >> flag2 = 1; >> } >> i++;j--; >> } >> if (sum<0) //if cur1->data + cur2->data < key >> { >> if(cur1->left == NULL) >> { >> cur1 = cur1->right; >> flag1 = 0; >> } >> else if(p1->right == cur1) >> { >> p1->right = NULL; >> cur1 = cur1->right; >> flag1 = 1; >> } >> i++; >> } >> if(sum>0)//if cur1->data + cur2->data > key >> { >> if(cur2->right == NULL) >> { >> cur2 = cur2->left; >> flag2 = 0; >> } >> else if(p2->left == cur2) >> { >> p2->left = NULL; >> cur2 = cur2->left; >> flag2 = 1; >> } >> j--; >> } >> } >> } >> } >> >> //final correction of the links can be done again >> } >> >> int checksum ( node *c1,node *c2,int key) >> { >> if(c1->data+c2->data == key) >> return 0; >> else if(c1->data+c2->data > key) >> return 1; >> else >> return -1; >> }* >> >> >> >> -- >> *Piyush Sinha* >> *IIIT, Allahabad* >> ** >> *+91-7483122727* >> *Never say NEVER <https://www.facebook.com/profile.php?id=100000655377926> >> * >> >> -- >> 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. >> > > > > -- > Regards,* > Aanchal Goyal*. > > -- > 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. > > -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * <https://www.facebook.com/profile.php?id=100000655377926> "NEVER SAY NEVER" * -- 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.
